自动搬运

查看原文

来自洛谷，原作者为

	Floating__Dream 所爱即山海，山海不可平

搬运于2025-08-24 21:22:19，当前版本为作者最后更新于2018-08-02 10:11:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

连接一条边----连通块数量减一 k个连通块-----连（n-k）边 运用kruskal算法的思想：每次连可以连的边中代价最小的 （贪心） 使用 并查集维护

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
int n,k,m;
int fa[1000050];
struct node {
	int x;
	int y;
	int l;
} a[1000005];
int cmp( const void *a , const void *b ) {
	struct node *c = (node *)a;
	struct node *d = (node *)b;
	return c->l - d->l;
}
int find(int x)
{
	if(x!=fa[x])
	fa[x]=find(fa[x]);
	return fa[x];
}
void work(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x==y)
	return;
	fa[x]=y;
}
int main() {
	cin>>n>>m>>k;
	for(int i=0; i<m; i++) {
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].l);
	}
	qsort(a,m,sizeof(a[0]),cmp);
	for(int i=1;i<=n;i++)
	fa[i]=i;
	int num=n-k;
	int ans=0;
	for(int i=0;i<m;i++)
	{
		if(num==0)
		break;
		int aaa=find(a[i].x);
		int wzx=find(a[i].y);
		if(aaa!=wzx)
		{
			work(a[i].x,a[i].y);
			ans+=a[i].l;
			num--;
		}
	}
	if(num)
	cout<<"No Answer"<<endl;
	else
	cout<<ans<<endl;
}