解题报告：luogu P1525

题目链接:P1525 关押罪犯
感觉自己海星，然后...

不要嘲讽我啊
并查集的运用，感觉十分巧妙。
我们在记录父亲是，还要记录敌人!
我们再贪心搞一搞，就能过了。
如果这两个罪犯不在同一个监狱里，就分配，如果已经在同意监狱里，由于前面我们已经尽量让代价高的符合条件，此时的代价就是答案了。

(Code):

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
#define read(x) scanf("%d",&x)

int n,m;
struct node
{
	int x,y,z;	
}a[1000005];
int f[20005],b[20005];

void init(int n){for(int i=1;i<=n;i++) f[i]=i,b[i]=0;}
int getf(int u){return f[u]==u?u:f[u]=getf(f[u]);}
void merge(int u,int v){int t1=getf(u),t2=getf(v);if(t1^t2) f[t2]=t1;}

bool cmp(node a,node b){return a.z>b.z;}

int main()
{
	read(n),read(m);
	init(n);
	for(int i=1;i<=m;i++) read(a[i].x),read(a[i].y),read(a[i].z);
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		if(getf(a[i].x)==getf(a[i].y)){printf("%d
",a[i].z);return 0;}
		if(!b[a[i].x]) b[a[i].x]=a[i].y;
		else merge(b[a[i].x],a[i].y);
		if(!b[a[i].y]) b[a[i].y]=a[i].x;
		else merge(b[a[i].y],a[i].x);
	}
	printf("0
");
	return 0;
}

(是不是有点压行啊......