kruskal代码,30分求debug
查看原帖
kruskal代码,30分求debug
533498
yyyzrc123楼主2023/10/8 17:11
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,tot,ans[100010],answer;
bool colour[10000010];
struct Node{int u,v,w;} e[100010];
bool cmp(Node a,Node b){return a.w<b.w;}
void add(int u,int v,int w){e[tot].u=u;e[tot].w=w;e[tot].v=v;tot++;}
void add2(int i){ans[cnt]=i;cnt++;}
//void print(int i){cout<<e[i].u<<' '<<e[i].v<<'\n';}
int main(){
	cin>>n>>m;
	for(int i=0;i<m;i++){int u,v,w;cin>>u>>v>>w;add(u,v,w);}
	sort(e,e+m,cmp);
	for(int i=0;i<m&&cnt<=n-1;i++){
		if(colour[e[i].u]&&colour[e[i].v])continue;
		add2(i);
		colour[e[i].u]=colour[e[i].v]=1;
	}
//	for(int i=0;i<cnt;i++)print(ans[i]);
	if(cnt<n-1){
		cout<<"orz";
		return 0;
	}
	for(int i=0;i<cnt;i++) answer+=e[i].w;
	cout<<answer;
    // cout<<"orz";
} 
2023/10/8 17:11
加载中...