分析
使用Kruskal算法计算最小连通图。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,x,fa[N],ans;
struct node{
int a,b,w;
bool operator<(const node& p) //排序函数
{
return w<p.w;
}
};
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
for(int i=0;i<N;i++) fa[i]=i;
vector<node> edges;
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>x;
if(i!=j) edges.push_back({i,j,x});
}
}
sort(edges.begin(),edges.end()); //按边权从小到大排序
for(int i=0;i<int(edges.size());i++)
{
int a=edges[i].a,b=edges[i].b,w=edges[i].w;
int faa=find(a),fbb=find(b);
if(faa!=fbb)
{
fa[faa]=fbb; //并查集操作
ans+=w; //把边权加入到答案中
}
}
cout<<ans;
return 0;
}