最小生成树反一反就好了，优先队列那快比较函数改成从大到小即可。纯板子题。
#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <functional> #include <iostream> #include <map> #include <queue> #include <stack> #include <string> #include <vector> //#include<unordered_map> #define lowbit(x) ((x) & -(x)) using namespace std; typedef long long ll; typedef unsigned long long ull; const int N = 5e4 + 10, NN = 2e3 + 10, INF = 0x3f3f3f3f, LEN = 20; const ll MOD = 1e9 + 7; const ull seed = 31; inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x * f; } struct Edge { int next, to, dis; bool friend operator<(const Edge& a, const Edge& b) { return a.dis < b.dis; } } edge[N]; int n, m, num_edge, ans, cnt; int head[N]; bool vis[N]; void add_edge(int from, int to, int dis) { edge[num_edge].next = head[from]; edge[num_edge].to = to; edge[num_edge].dis = dis; head[from] = num_edge++; } void init() { num_edge = ans = cnt = 0; memset(head, -1, sizeof head); memset(vis, false, sizeof vis); } bool prim() { priority_queue<Edge> q; ++cnt; vis[1] = true; for (int i = head[1]; i != -1; i = edge[i].next) { int v = edge[i].to; if (vis[v]) continue; q.push(edge[i]); } while (!q.empty()) { int point = 0; Edge u = q.top(); point = u.to; if (vis[point]) { q.pop(); continue; } vis[point] = true; ans += u.dis; ++cnt; if (cnt == n) break; for (int i = head[point]; i != -1; i = edge[i].next) { int v = edge[i].to; if (vis[v]) continue; q.push(edge[i]); } } if (cnt == n) return true; else return false; } int main() { while (~scanf("%d%d", &n, &m)) { init(); for (int i = 1; i <= m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); add_edge(u, v, w); add_edge(v, u, w); } if (prim()) printf("%d\n", ans); else printf("-1\n"); } }