并查集水题求助
查看原帖
并查集水题求助
315205
Kniqht楼主2023/8/28 08:54

这样与题解的做法有什么区别吗?60pts 求hack

我这样写也是把敌人合并啊

#include<bits/stdc++.h> 
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,p[N];
struct Node{
    int x,y,w;
}a[N];
bool cmp(Node a1,Node a2){
    return a1.w>a2.w;
}
int find(int x){
    return x==p[x]?x:p[x]=find(p[x]);
}
void merge(int x,int y){
    int pa=find(x),pb=find(y);
    p[pa]=pb;
}

signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n*2;i++) p[i]=i;
	for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].w);
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++){
	    if(find(a[i].x)==find(a[i].y)){
	        printf("%lld",a[i].w);
	        return 0;
	    }
	    else merge(a[i].x,a[i].y),merge(n+a[i].x,n+a[i].y);
	}
	printf("0");
    return 0;   
}

另外这种方法为什么一定正确,

2023/8/28 08:54
加载中...