问题描述
下面是一个8个结点的无向图的邻接矩阵表示,其中第 i 行第 j 列表示结点 i 到结点 j 的边长度。当长度为 0 时表示不存在边。
请问,这个图的最小生成树大小的多少?
样例
0 9 3 0 0 0 0 9
9 0 8 1 4 0 0 0
3 8 0 9 0 0 0 0
0 1 9 0 3 0 0 5
0 4 0 3 0 7 0 6
0 0 0 0 7 0 5 2
0 0 0 0 0 5 0 4
9 0 0 5 6 2 4 0
/*
Kruskal算法
kruscal算法是用于生成最小生成树的常见算法,
最小生成树也就是在包含图中所有节点的树中,边权和最小的那棵树
将所有的边长按从小到大排列,每次取最小的边连接两节点,
若两节点已经处于连通状态,则不连接
循环上面的步骤,知道所有节点都已经连通,所有边之和就是答案
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int n = 8;
int p[n],ans = 0;
vector<pair<int,int>> a;
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
for(int i = 0;i < n ; i ++) p[i] = i;
for(int i = 0 ; i < n ; i ++)
for(int j = 0; j < n ; j ++)
{
int len;
cin >> len;
if(len) a.push_back({len,i * 100 + j});
}
sort(a.begin(),a.end());
for(int i = 0 ; i < a.size() ; i ++)
{
int len = a[i].first;
int x = a[i].second / 100;
int y = a[i].second % 100;
if(find(x) != find(y))
{
p[p[x]] = p[y];
ans += len;
printf("%d --> %d (%d)\n", x, y, len);
}
}
cout << ans << endl;
return 0;
}