社区讨论
一个问题,求助dalao
P1195口袋的天空参与者 2已保存回复 10
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 10 条
- 当前快照
- 1 份
- 快照标识符
- @mi865njv
- 此快照首次捕获于
- 2025/11/21 09:16 4 个月前
- 此快照最后确认于
- 2025/11/21 09:16 4 个月前
- 如何保证生产了k棵树呢?
- kruskal算法里 sum记录了已选入MST的边数,且易知一共要选n-k条边 (类比氨基酸),但是在选择的时候如何保证选的边为独立的棵树?
- 如下图是否合法?

(已ac)
CPP#include<bits/stdc++.h>
using namespace std;
const int maxn=200001;
//边数
int nx,m;
int sum;//记录有多少条边了
int ans;//记录MSL的边权之和
int f[maxn];
int u,v,kk;
struct d
{
int from;
int to;
int dis;
}edge[maxn];//无向图
inline int find(int k)
{
if(f[k]!=k) f[k]=find(f[k]) ;
return f[k];
}
bool cmp(d a,d b)
{
return a.dis<b.dis;
}
inline bool kruskal()
{
for(int i=1;i<=nx;i++) f[i]=i;
sort(edge+1,edge+m+1,cmp);
for(int i=1;i<=m;i++)
{
u=find(edge[i].from);
v=find(edge[i].to);
if(u!=v)
{
ans+=edge[i].dis;
f[u]=v;
sum++;
if(sum==nx-kk)
{
cout<<ans;
return false;
}
}
}
return true;
}
int main()
{
cin>>nx>>m>>kk;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].dis);
}
if(kruskal()) cout<<"No answer";
return 0;
}
回复
共 10 条回复,欢迎继续交流。
正在加载回复...