用优先队列写kruskal却t了8个点求助
查看原帖
用优先队列写kruskal却t了8个点求助
206423
焚魂楼主2024/9/16 15:53

感觉不应该啊

#include<iostream>
#include<cstdio>
#include<queue>

using namespace std;

int n,m,k,f[5010],mst;
struct node{
	int u,v,w;
	bool operator < (const node &a) const {
		return w > a.w;
	}
};
priority_queue<node,vector<node> > q;
 
node getnode(int u,int v,int w) {
	return node{u,v,w};
} 

int find(int x) {
	if(f[x] != x) f[x] = find(f[x]);
	return f[x];
}

void unionn(int x,int y) {
	x = find(x);
	y = find(y);
	f[y] = x; 
}
 
int main() {
	cin >> n >> m;
	for(int i = 1;i <= m;i++) {
		int x,y,z;
		cin >> x >> y >> z;
		q.push(getnode(x,y,z));
	}
	
	for(int i = 1;i <= n;i++) f[i] = i;
	
	while(!q.empty()) {
		if(find(q.top().u) != find(q.top().v)) {
			k++;
			mst += q.top().w;
			unionn(q.top().u,q.top().v);
			q.pop();
		}
		if(k == n-1) break;
	}
	
	cout << mst;
	
	return 0;
}
2024/9/16 15:53
加载中...