P1525 关押罪犯

P1525 关押罪犯

题解

这题用并查集做鸭

考虑到一定要把两个怨气值尽量大的人分开，我们先把怨气值从小到大排个序

此处处理：两个人有怨，就连边，记下权值，然后sort排序

然后一条边一条边处理

（1）对于两个人，如果他们都没有敌人，那就互相标记为敌人

（2）如果一个a有敌人，另一个b没敌人，那就把b的敌人记为a，然后把敌人的敌人置为朋友

（3）如果遇到两个人必须安排到一个监狱（也就是本应该成为敌人，但是必须成为朋友），那么此时输出边的权值就完事了，不然最后就是没有冲突

代码

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    int ans=0;
    char last=' ',ch=getchar();
    while(ch<'0'||ch>'9') last=ch,ch=getchar();
    while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();
    if(last=='-') ans=-ans;
    return ans; 
}

int n,m;
int fa[20010],di[20010];
struct node
{
    int u,v,w;
}edge[100010];

int find(int x)
{
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}

void hql(int x,int y)
{
    int fa1=find(x);
    int fa2=find(y);
    fa[fa1]=fa2;
}

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

int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        edge[i].u =read();
        edge[i].v =read();
        edge[i].w =read();
    }
    
    sort(edge+1,edge+m+1,cmp);
    
    for(int i=1;i<=m;i++)
    {
        int a=edge[i].u ,b=edge[i].v ;
        if(find(a)==find(b)) 
        {
            printf("%d
",edge[i].w );
            return 0;
        }
        else
        {
            if(!di[a])
            {
                di[a]=b;
                if(!di[b]) di[b]=a;
                else hql(a,di[b]);
            }
            else
            {
                hql(b,di[a]);
                if(!di[b]) di[b]=a;
                else hql(a,di[b]);
            }
        }
    }
    
    printf("0
");
    
    return 0;
}