[NOIP2010提高组]关押罪犯(被自己蠢哭了)

[NOIP2010提高组]关押罪犯
题目：洛谷P1525、Vijos P1776、codevs1069。

题目大意：有一些罪犯，两个罪犯之间可能会发生冲突，冲突有个影响力，而如果两个罪犯在不同监狱里，就可以避免冲突。现在有两个监狱，要你安排一种关押罪犯的方式，使得影响力最大的一次冲突影响力最小。

思路：贪心加并查集。

代码：

#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
int f[20005];
int enemy[20005];
struct node
{
    int a,b,c;
}p[100005];
bool cmp(node x,node y)
{
    return x.c>y.c;
}
int tofind(int a)
{
    if(f[a]==-1)
        return a;
    f[a]=tofind(f[a]);
    return f[a];
}
void tojoin(int a,int b)
{
    int r1=tofind(a);
    int r2=tofind(b);
    if (r1!=r2)
        f[r1]=r2;
}
int main()
{
    int n,m,ans;
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        f[i]=-1;
        enemy[i]=0;
    }
    for(int i=1;i<=m;i++)
        cin>>p[i].a>>p[i].b>>p[i].c;
    sort(p+1,p+m+1,cmp);//就是在sort这里被自己蠢哭了 呜呜呜呜呜
    for (int i=1;i<=m;i++)
    {
        int x=tofind(p[i].a);
        int y=tofind(p[i].b);
        if (x==y)
        {
            ans=p[i].c;
            break;
        }
        if (enemy[x]==0)
            enemy[x]=y;
        else
            tojoin(y,enemy[x]);
        if (enemy[y]==0)
            enemy[y]=x;
        else
            tojoin(x,enemy[y]);
    }
    cout<<ans<<endl;
    return 0;

}