首页 > 其他 > 详细

P1525 关押罪犯

时间:2019-07-08 12:56:40      阅读:131      评论:0      收藏:0      [点我收藏+]

 

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\n",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\n");
    
    return 0;
}

 

P1525 关押罪犯

原文:https://www.cnblogs.com/xiaoyezi-wink/p/11149929.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!