Kruskal70ts求助
查看原帖
Kruskal70ts求助
683768
Allen_yang楼主2023/1/11 10:03
#include<iostream>
#include<algorithm>
using namespace std;
struct MST{
	int u,v,w;
	bool operator<(const MST& m){
		return w<m.w;
	}
};

MST graph[10005];
int F[1005];
int n,m,k;
long long mst=0;

int find(int x){
	if(F[x]==x)return x;
	return F[x]=find(F[x]);
}
void merge(int x,int y){
	int fx=find(x);
	F[fx]=find(y);
}

bool Kruskal(){
	for(int i=1;i<=n;i++)F[i]=i;
	int cnt=0;
	sort(graph,graph+m);
	for(int i=1;i<=m;i++){
		int u=graph[i].u,v=graph[i].v;
		if(find(u)!=find(v)){
			merge(u,v);
			mst+=graph[i].w;
			cnt++;
			if(cnt==n-k)return true;
		}
	}
	return false;
}
int main(){
	cin >> n >> m >> k;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		graph[i].u=u;
		graph[i].v=v;
		graph[i].w=w;
	}
	if(Kruskal())cout << mst;
	else cout << "No Answer";
	return 0;
}
2023/1/11 10:03
加载中...