输出和下载的数据一样,判WA?
查看原帖
输出和下载的数据一样,判WA?
242490
lyc呐楼主2020/8/24 10:50
#include<bits/stdc++.h>
using namespace std;
struct unionFind{	//并查集 
	int bin[20005];
	unionFind(){
		for(int i=0;i<20005;i++)
			bin[i]=i;
	}
	int anc(int x){
		if(bin[x]==x)
			return x;
		bin[x]=anc(bin[x]);
		return bin[x];
	}
	void add(int x,int y){
		bin[anc(x)]=anc(y);
	}
	bool check(int x,int y){
		if(anc(x)==anc(y))
			return true;
		return false;
	}
};
struct node{
	int x=0,y=0,z=0;
};
bool comp(node x,node y){
	return x.z>y.z;
}
int main(){
	int n,m;
	unionFind uf;
	cin>>n>>m;
	node arr[100005];
	int b[20005];
	for(int i=0;i<m;i++)
		scanf("%d%d%d",&arr[i].x,&arr[i].y,&arr[i].z);
	sort(arr,arr+m,comp);
	for(int i=0;i<=m;i++){	 
			if(!b[arr[i].x])
				b[arr[i].x]=arr[i].y;
			else
				uf.add(b[arr[i].x],arr[i].y);
			if(!b[arr[i].y])
				b[arr[i].y]=arr[i].x;
			else
				uf.add(b[arr[i].y],arr[i].x);
		if(uf.check(arr[i].x,arr[i].y)){	//矛盾出现,输出结束 
			printf("%d",arr[i].z);
			break;
		}		
	}	
}
2020/8/24 10:50
加载中...