题意：求一个图的最小生成树的权值，其中有一些边是已经连通的 思路：在没连通的边中用kruskal求出最小生成树即可
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; const int maxn = 100005; const int inf = 0x3f3f3f3f; int u[maxn], n, q; struct node { int u, v, w; node(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {} }edge[maxn]; bool cmp(node x, node y) { return x.w < y.w; } int ufind(int x) { if (u[x] != x) { u[x] = ufind(u[x]); } return u[x]; } void unite(int x, int y) { u[ufind(x)] = ufind(y); } int main() { while (cin >> n) { int cnt = 0, k = 0, res = 0; for (int i = 1; i <= n; i++) { u[i] = i; for (int j = 1; j <= n; j++) { int w; cin >> w; if (i != j) edge[cnt++] = node(i, j, w); } } cin >> q; for (int i = 0; i < q; i++) { int x, y; cin >> x >> y; if (ufind(x) != ufind(y)) { unite(x, y); k++; } } sort(edge, edge+cnt, cmp); for (int i = 0; i < cnt; i++) { int x = edge[i].u, y = edge[i].v; if (ufind(x) != ufind(y)) { unite(x, y); k++; res += edge[i].w; } if (k == n-1) break; } cout << res << endl; } return 0; }