从邻接矩阵中提取出边, 然后跑一边 kruscal
- #include<iostream>
- #include<algorithm>
- using namespace std;
- struct node
- {
- int x,y,w;
- };
- int cnt=0;// 记录边数
- node a[100*100];// 记录边
- int fa[110];// 记录并查集
- int finds(int x)// 并查集找祖先
- {
- while(fa[x]!=x)
- {
- x=fa[x];
- }
- return x;
- }
- bool cmp(node a,node b)
- {
- return a.w<b.w;
- }
- int main(void)
- {
- int n;
- cin>>n;
- for(int i=1;i<=n;i++)// 提取边
- {
- for(int j=1;j<=n;j++)
- {
- int t;
- cin>>t;
- if(j>i)// 如果列大于行
- {
- a[cnt].x=i;
- a[cnt].y=j;
- a[cnt].w=t;
- cnt++;
- }
- }
- }
- sort(a,a+cnt,cmp);// 排序
- // 以上处理边
- for(int i=1;i<=n;i++)
- {
- fa[i]=i;
- }// 初始化并查集
- int res=0;
- for(int i=0;i<cnt;i++)// 找最小生成树
- {
- int from=a[i].x;
- int to=a[i].y;
- int weight=a[i].w;
- int f1=finds(from);
- int f2=finds(to);
- if(f1!=f2)
- {
- res+=weight;
- fa[f1]=f2;//union
- }
- }
- cout<<res;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3394783.html