- #include<iostream> // 利用最小生成树中的 kruskal 算法
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- int bin[120];
- struct node{
- int val,x,y;
- }a[10010];
- int cmp(struct node a,struct node b){
- return a.val<b.val;
- }
- int find(int x){
- if(bin[x]==x) return x;
- else return bin[x]=find(bin[x]);
- }
- void unite(int x,int y){
- x=find(x),y=find(y);
- bin[x]=y;
- }
- int main(){
- int n,d;
- struct node c;
- while(cin>>n){
- int k=0;
- for(int i=1;i<=n;i++) // 利用并查集的知识防止生成圈, 若生成圈则一定不是最小
- bin[i]=i;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- {
- scanf("%d",&d);
- if(j>i) a[k].val=d,a[k].x=i,a[k].y=j,k++;
- }
- sort(a,a+k,cmp); // 对边的长度进行排序
- int sum=0;
- for(int i=0;i<k;i++){
- // 对边从小到大进行遍历
- if(find(bin[a[i].x])!=find(bin[a[i].y])) unite(bin[a[i].x],bin[a[i].y]),sum+=a[i].val; // 若不会生成圈, 则放入集合
- }
- printf("%d\n",sum);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3184086.html