【并查集】【P1525】关押罪犯

Description

Input

Output

Sample Input

Sample Output

Hint

Solution

　　非常显然的并查集题目，在本题中，对于每个罪犯i，维护两个信息：必须要和他关在一起的罪犯的集合，以及和他有仇的罪犯的集合，由于监狱只有两个，所以和他有仇的罪犯一定被关在同一个集合里面。sort一遍贪心从上到下扫描。对于不得不管起来的两个有仇的人即为答案。

Code

#include<cstdio>

#include<algorithm>

namespace read{

    void imop(int&x){

        char ch=getchar();

        while(ch<''||ch>'') ch=getchar();

        while(ch>=''&&ch<='')   x=x*+ch-'',  ch=getchar();

        return;

    }

    void op(int&x){

        char ch=getchar();

        int f=;

        while(ch<''||ch>''){

            if(ch=='-') f=-;

            ch=getchar();

        }

        while(ch>=''&&ch<='')   x=x*+ch-'',  ch=getchar();

        x*=f;

        return;

    }

}

namespace fusu{

    const int maxn =  , maxm = ;

    struct Crim{

        int a,b,value;

    };

    Crim criminal[maxm];

    int n,m;

    inline bool cmp(Crim a,Crim b){return a.value<b.value;}

    int frog[maxn],enemy[maxn];

    inline int find(int x){

        if(frog[x]^x)    frog[x]=find(frog[x]);

        return frog[x];

    }

    void gather(int a,int b){

        int fa=find(frog[a]),fb=find(frog[b]);

        frog[fa]=fb;

        return;

    }

    void beginning(){

        for(int i=;i<=n;++i)

            frog[i]=i;

        return;

    }

    int doit(){

        read::imop(n);read::imop(m);

        for(int i=;i<=m;++i){

            read::imop(criminal[i].a);

            read::imop(criminal[i].b);

            read::imop(criminal[i].value);

        }

        std::sort(criminal+,criminal++m,cmp);

        beginning();

        do{

            int fa=find(frog[criminal[m].a]),fb=find(frog[criminal[m].b]);

            if(!(fa^fb)){

                printf("%d\n",criminal[m].value);

                return ;

            }

            if(!enemy[criminal[m].a])    enemy[criminal[m].a]=criminal[m].b;

                else gather(enemy[criminal[m].a],criminal[m].b);

            if(!enemy[criminal[m].b])    enemy[criminal[m].b]=criminal[m].a;

                else gather(enemy[criminal[m].b],criminal[m].a);

            --m;

        }while(m);

        printf("0\n");

        return ;

    }

}

int main(){

    return fusu::doit();

}

Summary

对于并查集中的补集法，对于每个个体记录多个信息，在合并时合并多个信息即可。

巴特西

【并查集】【P1525】关押罪犯

Description

Input

Output

Sample Input

Sample Output

Hint

Solution

Code

Summary

最新文章

热门文章