求问:为什么不能建双向边
查看原帖
求问:为什么不能建双向边
801391
_czx_楼主2023/11/5 19:20

建双向边 70pts, 建单向边 100pts,我不理解

#include<iostream>
#include<algorithm>
using namespace std;
int n,m,u,v,w;
struct edge{
	int x,y,w;
}e[8001];
int cnt,c;
void buildup(int u,int v,int w){
	e[++cnt].x = u;
	e[cnt].y = v;
	e[cnt].w = w;
}
bool cmp(edge a,edge b){
	return a.w < b.w;
}
int f[302];
int getf(int x){
	return x == f[x]? x:f[x] = getf(f[x]);
}
int main(){
	cin >> n >> m;
	for(int i= 1;i<=n;i++){
		f[i] = i;
	}
	for(int i = 1;i<=m;i++){
		cin >> u >> v >> w;
		buildup(u,v,w);
		//buildup(v,u,w);
	}
	sort(e+1,e+1+cnt,cmp);
	for(int i = 1;i<=cnt;i++){
		int f1 = getf(e[i].x),f2 = getf(e[i].y);
		if(f1 == f2) continue;
		f[f1] = f2;
		c++;
		if(c == n-1){
			cout << c << ' ' << e[i].w;
			return 0;
		}
	}
	cout << c << ' ' << e[m].w;
	return 0;
}
2023/11/5 19:20
加载中...