文章

17

粉丝

166

获赞

6

访问

144.5k

头像
kruskal算法
P1312 浙江大学机试题
发布于2021年2月27日 23:09
阅读数 8.9k

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
struct Edge
{
	int a, b, w;
	bool operator< (const Edge &W)const{return w < W.w;}
}edge[N];
int p[N];
int n, m;
int find(int x)
{
	if(p[x] != x) p[x] = find(p[x]);
	return p[x];
}
int main()
{
	while(cin >> n >> m)
	{
		if(n == 0) break;
		for(int i = 0; i < n; i++)
		{
			int a, b, w;
			cin >> a >> b >> w;
			edge[i] = {a, b, w};
		}
		sort(edge, edge + n);

		int cnt = 0, ans = 0;
		for(int i = 1; i <= m; i++) p[i] = i;
		for(int i = 0; i < n; i++)
		{
			int a = edge[i].a, b = edge[i].b, w = edge[i].w;
			a = find(a), b = find(b);
			if(a != b)
			{
				ans += w;
				cnt ++;
				p[a] = b;
			}
		}
		if(cnt < m - 1) cout << "?" << endl;
		else cout << ans << endl;
	}
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发