Luogu P1525 关押罪犯

Luogu P1525 关押罪犯

这又是道神奇的并查集。
先按愤怒值大小从大到小排列所有仇恨关系。
再判断每一组仇恨关系中两人是否可以分在两个监狱中。如果可以，就分开病把两人标记为彼此的敌人。如果不可以，就输出两人冲突的影响力。
但这里又有一个小技巧，就是把敌人的敌人与自己合并。（这个真的见得太多了）
最后如果始终没有冲突发生，就输出$0$即可。

#include<bits/stdc++.h>
#define N 20010
#define M 100010

using namespace std;

int n,m;
int fa[N],enemy[N];

struct node {
	int a,b,c;
}angry[M];

bool cmp(node x,node y) {
	return x.c>y.c;
}

int Find(int x) {
	return fa[x]==x?x:fa[x]=Find(fa[x]);
}

bool Judge(int x,int y) {
	if(Find(x)==Find(y)) {
		return true;
	}
	else {
		return false;
	}
}

void Merge(int x,int y) {
	fa[Find(fa[y])]=Find(fa[x]);
	return;
}

void Read() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) {
		scanf("%d%d%d",&angry[i].a,&angry[i].b,&angry[i].c);
	}
	return;
}

void Init() {
	for(int i=1;i<=n;i++) {
		fa[i]=i;
	}
	return;
}

void Solve() {
	for(int i=1;i<=m;i++) {
		if(Judge(angry[i].a,angry[i].b)) {
			printf("%d",angry[i].c);
			return;
		}
		if(!enemy[angry[i].a]) {
			enemy[angry[i].a]=angry[i].b;
		}
		else {
			Merge(enemy[angry[i].a],angry[i].b);
		}
		if(!enemy[angry[i].b]) {
			enemy[angry[i].b]=angry[i].a;
		}
		else {
			Merge(enemy[angry[i].b],angry[i].a);
		}
	}
	printf("0");
	return;
}

int main()
{
	Read();
	Init();
	sort(angry+1,angry+m+1,cmp);
	Solve();
	return 0;
}