社区讨论

挂0了,求调。。

P1195口袋的天空参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lzkp99m2
此快照首次捕获于
2024/08/08 11:09
2 年前
此快照最后确认于
2024/08/08 11:48
2 年前
查看原帖
CPP
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,k,cnt=1,ans,f[5010];
struct edge{
	int u,v,w;
}e[200010];
int find(int k)
{
	if(f[k]==k) return k;
	else return f[k]=find(f[k]);
}
bool cmp(edge a,edge b)
{
	return a.w < b.w;
}
void kruskal()
{
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		int eu=find(e[i].u);
		int ev=find(e[i].v);
		if(eu==ev) continue;
		ans+=e[i].w;
		f[ev]=eu;
		if(++cnt==k)
		{
			cout<<ans;
			exit(0);
		}
	}
	cout<<"No Answer";
}
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
		cin>>e[i].u>>e[i].v>>e[i].w;
	for(int i=1;i<=n;i++) f[i]=i;
	kruskal();
}

回复

2 条回复,欢迎继续交流。

正在加载回复...