题目描述
blablabla
Kruskal算法例题
样例
输入
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
输出
28
C++ 代码
#include <bits/stdc++.h>
using namespace std;
struct point
{
int x, y, v;
};
point a[10010];//定义结构体表示边
int fa[101];
int n, x, m, ans, k;
int find(int x) //并查集 合并
{
if(fa[x] == x) return x;
fa[x] = find(fa[x]);
return fa[x];
}
bool cmp(const point &a, const point &b) //自定义比较函数
{
return (a.v < b.v);
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
cin >> x;
if(x) m++, a[m].x = i, a[m].y = j, a[m].v = x; //把i到j边权输入(x != 0 等价于 i != j)
}
for(int i = 1; i <= n; i++) fa[i] = i; //初始化并查集
sort(a + 1, a+m + 1, cmp); //升序排序
for(int i = 1; i <= m; i++){
int a = finda[i].x, b = find(a[i].y);
if(a != b){ ///并查集 查询
fa[a] = b; ///判断是否在同一集合
ans += a[i].v; //最小边权累加
k++;
}
//if(k == n - 1) break; //无法连接情况的特判(没用上)
}
cout << ans;
return 0;
}