#为啥一个都过不去,求大佬教教,或者告诉下测试数据都行,球球了
查看原帖
#为啥一个都过不去,求大佬教教,或者告诉下测试数据都行,球球了
733058
hui6bc楼主2022/5/29 12:44
#include<iostream>
#include<algorithm>
using namespace std;
#define N 10005
int k;
struct node
{
	int x, y, l;
}e[N];
struct num
{
	int i, sum,k;
}arr[1005];
bool cmp(node aa, node bb)
{
	return aa.l < bb.l;
}
int findx(int x)
{
	int r = x;
	while (r != arr[r].i)
		r=arr[r].i;
	return r;
}
void merge(node aa)
{
	int fx = findx(aa.x);
	int fy = findx(aa.y);
	if (fx != fy)
	{
		arr[fy].i = fx;
		if (arr[fx].k != k-1)
		{
			arr[fx].k++;
			arr[fx].sum += aa.l;
		}
	}
}
int main()
{
	int n, m,i,min=0x7fffffff;
	cin >> n >> m >> k;
	for (i = 1; i <= m; i++)
	{
		cin >> e[i].x >> e[i].y >> e[i].l;
	}
	for (i = 1; i <= n; i++)
	{
		arr[i].i = i;
	}
	sort(e + 1, e+ m + 1, cmp);
	for (i = 1; i <= m; i++)
	{
		merge(e[i]);
	}
	for (i = 1; i <= n; i++)
	{
		if (arr[i].i == i && arr[i].k == k-1)
		{
			if (arr[i].sum < min)
			{
				min = arr[i].sum;
			}
		}
	}
	if (min == 0x7fffffff)
	{
		cout << "No Answer" << endl;
	}
	else
		cout << min << endl;
	return 0;
}
2022/5/29 12:44
加载中...