题意:
...不多说
注意:
输入是矩阵...
有了并查集, 怎么也不想写Prim了....
#include <cstdio> #include <vector> #include <algorithm> using namespace std; const int MAXN = 105; int f[MAXN]; int n; typedef struct edge { int u,v,w; edge(){} edge(int _u, int _v, int _w):u(_u),v(_v),w(_w){} }edge; vector<edge> g; bool cmp(edge a, edge b) { return a.w<b.w; } int find_set(int x) { if(f[x]!=x) f[x] = find_set(f[x]); return f[x]; } int Kruskal() { sort(g.begin(),g.end(),cmp); for(int i=0;i<n;i++) f[i] = i; int ans = 0; for(int i=0;i<g.size();i++) { int u = g[i].u, v = g[i].v; u = find_set(u), v = find_set(v); if(u==v) continue; f[u] = v; ans += g[i].w; } return ans; } int main() { while(scanf("%d",&n)==1) { g.clear(); for(int i=0;i<n;i++) { for(int j=0,w;j<n;j++) { scanf("%d",&w); if(i<j) g.push_back(edge(i, j, w)); } } printf("%d\n",Kruskal()); } }