P1525 关押罪犯

我会带着你远行 2023-06-01 08:45 3阅读 0赞

[P1525 关押罪犯][P1525]

提供一种做法：并查集。

考虑a和b之间有仇恨关系，存入结构体中。

因为有对应关系，且结构体带有权值，答案求最值，考虑排序。

#### 如果把仇恨值最大的放在一个监狱，而仇恨值比他们小的放在不同监狱，显然不可能是ans。 ####

#### 所以我们把仇恨值从大到小排序，对于每个结构体，我们把两个人分开放。 ####

#### 如果发现，这两个人已经在一个监狱，输出结果则为ans。 ####

代码中for到m+1的原因是为了输出0（如果前m组关系都能处理好是没有printf的）而第m+1因为初始化赋值是0，根据程序可以输出0。

二分图染色法同理。

1 #include <iostream>
     2 #include <cstdio>
     3 #include <algorithm>
     4 using namespace std;
     5 struct date{
        int x,y,hate;}a[100005];
     6 int n,m,f[20005],b[20005];
     7 inline bool cmp(date a1,date a2){
        return a1.hate>a2.hate;}
     8 inline int find(int x){
        return f[x]==x?x:f[x]=find(f[x]);}
     9 inline int ri(){
    10     char c=getchar();int x=0,w=1;
    11     while(!isdigit(c)){
        if(c=='-')w=-1;c=getchar();}
    12     while( isdigit(c)){x=(x<<3)+(x<<1)+c-48;c=getchar();}
    13     return x*w;
    14 }
    15 int main(){
    16     n=ri(),m=ri();
    17     for(int i=1;i<=n;i++)f[i]=i;
    18     for(int i=1;i<=m;i++)a[i].x=ri(),a[i].y=ri(),a[i].hate=ri();
    19     sort(a+1,a+m+1,cmp);
    20     for(int i=1;i<=m+1;i++){
    21         if(find(a[i].x)==find(a[i].y)){printf("%d",a[i].hate);break;}
    22         else 
    23         !b[a[i].x]?b[a[i].x]=a[i].y:f[find(b[a[i].x])]=find(a[i].y),
    24         !b[a[i].y]?b[a[i].y]=a[i].x:f[find(b[a[i].y])]=find(a[i].x);
    25     }
    26     return 0;
    27 }

简单解释一下l23，l24

因为压的有点bt。。

如果说x的敌人没有被标记过，那么x的敌人赋值为y。

如果标记过，把x的敌人和y扔在一个监狱里（秉承敌人的敌人就是朋友……），也就是一般上的union函数。我好像写过最小生成树的代码？？参见。

l24同理。

转载于:https://www.cnblogs.com/flicker-five/p/11480293.html

[P1525]: https://www.luogu.org/problem/P1525