#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<cstring>//测试 using namespace std; const int maxn = 10050; int m,n,k; struct edge{ int a,b; int v; }s[maxn]; int pre[maxn]; bool cmp(edge a,edge b){return a.v < b.v;} int Find(int a){ int root = a; int tmp; while(root != pre[root])root = pre[root]; while(a != root){ tmp = a; a = pre[a]; pre[tmp] = root; } return root; } void combine(int a,int b){ int x = Find(a); int y = Find(b); if(x > y) swap(x,y); pre[y] = x; } void kruskal(){ int ans = 0; for(int i=0;i<k;i++){ if(Find(s[i].a)!=Find(s[i].b)){ combine(s[i].a,s[i].b); ans += s[i].v; } } printf("%d\n",ans); } int main(){ while(~scanf("%d",&n)) { k=0; for(int i=0;i<=n;i++) { pre[i]=i; } for(int i=0;i<n;i++) { for(int j=0;j<n;j++){ int a; scanf("%d",&a); s[k].a=i; s[k].b=j; s[k++].v=a; } } sort(s,s+k,cmp); kruskal(); } return 0; } |
Double click to view unformatted code.