最小生成树
  • 板块学术版
  • 楼主uFTvL9
  • 当前回复18
  • 已保存回复18
  • 发布时间2022/1/26 11:57
  • 上次更新2023/10/28 10:54:31
查看原帖
最小生成树
411963
uFTvL9楼主2022/1/26 11:57

如下为一个裸的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;
}
2022/1/26 11:57
加载中...