如下为一个裸的Kruskal,它哪里不对了呢?
//#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
inline int Kruskal();
struct edge
{
int from;
int to;
int value;
};
int f[200000];
inline int find(int x) {
if(f[x] == x)//他上司就是他自己
return x;//找到上司了
return find(f[x]);//不然接着往下找
}
int N;
int _map[300][300];
int main(void) {
ios::sync_with_stdio(false);
std::cin.tie(0);
cin >> N;
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
cin >> _map[i][j];//存储邻接矩阵
int ans_Kruskal = Kruskal();
cout << ans_Kruskal << endl;
return 0;
}
inline bool cmp(edge o1, edge o2) {
return o1.value < o2.value;
}
inline int Kruskal() {
int res = 0;
int cnt = 0;
for (int i = 0; i <= N; ++i)
f[i] = i;//初始化并查集,使每个人的上司是自己
edge Edge[N];
int node = 0;
for(int i = 0; i < N; i++)
for(int j = 0; j < i; j++){
Edge[node].from = i;
Edge[node].to = j;
Edge[node].value = _map[i][j];
node++;
}
sort(Edge, Edge + N, cmp);
for(int i = 0; i < N; i++) {
int from = Edge[i].from;
int to = Edge[i].to;
int value = Edge[i].value;
from = find(from);
to = find(to);
if(from != to) {//如果他们没有在一个集合内
f[from] = to;//加入他
res += value;//边权值增长
cnt++;//边数增加
}
}
if(cnt < N-1){cout << "Impossible";return INF;}
return res;
}