社区讨论

一个问题,求助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 条回复,欢迎继续交流。

正在加载回复...