vijos 1776 关押罪犯

带权并查集+贪心。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxv 20050
#define maxe 100500
using namespace std;
struct edge
{
    int u,v,w;
}e[maxe];
int n,m,father[maxv],dis[maxv],fath_w[maxv];
bool cmp(edge x,edge y)
{
    return x.w>y.w;
}
int getfather(int x)
{
    int ret=father[x];
    if (father[x]!=x)
        ret=getfather(father[x]);
    dis[x]=dis[father[x]]^fath_w[x];fath_w[x]=dis[x];
    father[x]=ret;
    return father[x];
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    sort(e+1,e+m+1,cmp);    
    for (int i=1;i<=n;i++) father[i]=i;
    for (int i=1;i<=m;i++)
    {
        int u=e[i].u,v=e[i].v;
        int f1=getfather(e[i].u),f2=getfather(e[i].v);
        if (f1==f2)
        {
            if (!(dis[u]^dis[v]))
            {
                printf("%d
",e[i].w);
                return 0;
            }
        }
        else
        {
            father[f1]=f2;
            dis[f1]=fath_w[f1]=dis[e[i].u]^dis[e[i].v]^1;
        }
    }
    printf("0
");
    return 0;
}