专题五 并查集

专题地址:https://vjudge.net/contest/66964

A.Wireless Network

题目链接:https://vjudge.net/problem/POJ-2236
大意:南亚发生了一次地震。ACM (Asia Cooperated Medical 亚洲联合医疗队) 已经为膝上型电脑搭建了一个无线网络,但受到了一次不可预知的余震攻击,因此网络中的所有电脑都被破坏了。电脑被逐台修复,网络逐步恢复了工作。由于受到硬件的约束,每台电脑只能与距离它不超过 d 米的其它电脑直接通信。但每台电脑可被看作其它两台电脑的通信中转点,也就是说,如果电脑 A 和电脑 B 可以直接通信,或存在一台电脑 C 既可与 A 也可与 B 通信,那么电脑 A 和电脑 B 之间就能够通信。
在处理网络修复的过程中,工作人员们在任何一个时刻,可以执行两种操作:维修一台电脑,或测试两台电脑是否能够通信。请您找出全部的测试操作。
解题思路:并查集
代码

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
struct node
{
    int x,y;
}a[1010];
bool mp[1010][1010];
bool f[1010];
int pre[1010];

int root(int aa)
{
    if(pre[aa]!=aa)
    {
        pre[aa]=root(pre[aa]);
    }
    return pre[aa];
}

void zhan(int aa,int bb)
{
    if(root(aa)!=root(bb))
    {
        pre[root(aa)]=root(bb);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int n,d;
    cin>>n>>d;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
        pre[i]=i;
    }
    memset(mp,false,sizeof(mp));
    memset(f,false,sizeof(f));
    double l;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            l=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
            if(l<=d)
            {
                mp[i][j]=true;
            }
        }
    }
    char c;
//    for(int i=1;i<=n;i++)
//    {
//        for(int j=1;j<=n;j++)
//        {
//            cout<<mp[i][j];
//        }
//        cout<<endl;
//    }
    int p,q;
    while(cin>>c)
    {
        if(c=='O')
        {
            cin>>p;
            f[p]=true;
            for(int i=1;i<=n;i++)
            {
                if(mp[p][i]&&f[i])
                {
                    zhan(p,i);
                }
            }
        }
        if(c=='S')
        {
            cin>>p>>q;
            if(root(p)==root(q))
            {
                cout<<"SUCCESS"<<endl;
            }
            else
            {
                cout<<"FAIL"<<endl;
            }
        }
    }
    return 0;
}

B.The Suspects

题目链接:https://vjudge.net/problem/POJ-1611
题目大意:警察抓贩毒集团。有不同类型的犯罪集团,人员可能重复,集团内的人会相互接触。现在警察在其中一人(0号)身上搜出毒品,认为与这个人直接接触或通过其他人有间接接触的人都是嫌疑犯。问包括0号犯人共有多少嫌疑犯?
解题思路:并查集
代码

#include <iostream>
#include <cstring>
using namespace std;
int pre[30010];
int root(int a)
{
    if(a!=pre[a])
    {
        pre[a]=root(pre[a]);
    }
    return pre[a];
}
void zhan(int a,int b)
{
    if(root(a)!=root(b))
    {
        pre[root(a)]=root(b);
    }
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
        {
            break;
        }
        int d,u,v;
        for(int i=0;i<=n;i++)
        {
            pre[i]=i;
        }
        for(int i=0;i<m;i++)
        {
            cin>>d;
            for(int j=0;j<d;j++)
            {
                cin>>u;
                if(j==0)
                {
                    v=u;
                    continue;
                }
                zhan(u,v);
                v=u;
            }
        }
        int mmp=root(0);
        int ans=0;
        for(int i=0;i<n;i++)
        {
            if(root(i)==mmp)
            {
                ans++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

C.How Many Tables

题目链接:https://vjudge.net/problem/HDU-1213
又是一个板子题
代码

#include <iostream>

using namespace std;
int pre[1010];

int root(int a)
{
    if(a!=pre[a])
    {
        pre[a]=root(pre[a]);
    }
    return pre[a];
}

void zhan(int a,int b)
{
    if(root(a)!=root(b))
    {
        pre[root(a)]=root(b);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            pre[i]=i;
        }
        int a,b;
        for(int i=0;i<m;i++)
        {
            cin>>a>>b;
            zhan(a,b);
        }
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            if(pre[i]==i)
            {
                sum++;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

D.How Many Answers Are Wrong

题目链接:https://vjudge.net/problem/HDU-3038
带权并查集模板题,可以先做一下下一道题
代码

#include <iostream>

using namespace std;
struct node
{
    int pre,rel;
} p[200020];

int findd(int x)
{
    int tmp;
    if(x!=p[x].pre)
    {
        tmp=p[x].pre;
        p[x].pre=findd(p[x].pre);
        p[x].rel=p[x].rel+p[tmp].rel;
    }
    return p[x].pre;
}

int main()
{
    ios::sync_with_stdio(false);
    int n,m;
    int u,v,w;
    while(cin>>n>>m)
    {
        int ans=0;
        for(int i=0; i<=n; i++)
        {
            p[i].pre=i;
            p[i].rel=0;
        }
        for(int i=0; i<m; i++)
        {
            cin>>u>>v>>w;
            int roota=findd(u);
            int rootb=findd(v+1);
            if(roota==rootb&&p[u].rel+w!=p[v+1].rel)
                ans++;
            else if(roota<rootb)
            {
                p[rootb].pre=roota;
                p[rootb].rel=p[u].rel+w-p[v+1].rel;
            }
            else if(roota>rootb)
            {
                p[roota].pre=rootb;
                p[roota].rel=p[v+1].rel-w-p[u].rel;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

E.食物链

题目链接:https://vjudge.net/problem/POJ-1182
题目大意:动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。
现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述:
第一种说法是”1 X Y”,表示X和Y是同类。
第二种说法是”2 X Y”,表示X吃Y。
此人对N个动物,用上述两种说法,一句接一句地说出K句话,这K句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。
1) 当前的话与前面的某些真的话冲突,就是假话;
2) 当前的话中X或Y比N大,就是假话;
3) 当前的话表示X吃X,就是假话。
你的任务是根据给定的N(1 <= N <= 50,000)和K句话(0 <= K <= 100,000),输出假话的总数。

解题思路:带全并查集,dalao讲的已经很完美了https://blog.csdn.net/niushuai666/article/details/6981689

主要是利用了向量理解带全并查集中根节点与当前节点间的关系以及更新关系

代码

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
struct node
{
    int pre,rel;
}p[50050];
int n,k;
int ans=0;

int findd(int x)
{
    int tmp;
    if(x==p[x].pre)
        return x;
    tmp=p[x].pre;
    p[x].pre=findd(p[x].pre);
    p[x].rel=(p[x].rel+p[tmp].rel)%3;
    return p[x].pre;
}

int main()
{
    ios::sync_with_stdio(false);
    scanf("%d%d",&n,&k);
    for(int i=0;i<=n;i++)
    {
        p[i].pre=i;
        p[i].rel=0;
    }
    int d,x,y;
    for(int i=0;i<k;i++)
    {
        scanf("%d%d%d",&d,&x,&y);
        if(x==y&&d==2)
        {
            ans++;
            continue;
        }
        if(x>n||y>n)
        {
            ans++;
            continue;
        }
        int roota=findd(x);
        int rootb=findd(y);
        if(roota!=rootb)
        {
            p[rootb].pre=roota;
            p[rootb].rel=(p[x].rel+d-1+3-p[y].rel)%3;
        }
        else
        {
            if(d==1)
            {
                if(p[x].rel!=p[y].rel)
                {
                    ans++;
                    continue;
                }
            }
            if(d==2)
            {
                if((3-p[x].rel+p[y].rel)%3!=d-1)
                {
                    ans++;
                    continue;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

F.True Liars

题目链接:https://cn.vjudge.net/problem/POJ-1417
前半部分还是带权并查集的板子题,后半部分就冒出DP来了。。。头疼,存一波代码以后再完善

#include <iostream>

using namespace std;
struct node
{
    int pre,rel;
}p[1010];

int findd(int x)
{
    if(x!=p[x].pre)
    {
        int tmp=p[x].pre;
        p[x].pre=findd(p[x].pre);
        p[x].rel=(p[tmp].rel+p[x].rel)%2;
    }
    return p[x].pre;
}

int main()
{
    ios::sync_with_stdio(false);
    int n,p,q;
    while(cin>>n>>p>>q)
    {
        for(int i=0;i<=p+q;i++)
        {
            p[i].pre=i;
            p[i].rel=0;
        }
        int a,b,d;
        char c[5];
        for(int i=0;i<n;i++)
        {
            cin>>a>>b>>c;
            int roota=findd(a);
            int rootb=findd(b);
            if(c[0]=='y')d=0;
            else d=1;
            if(roota!=rootb)
            {
                p[rootb].pre=roota;
                p[rootb].rel=(p[a].rel+d+2-p[b].rel)%2;
            }
        }
        
    }
    return 0;
}

G.Supermarket

题目链接:https://cn.vjudge.net/problem/POJ-1456
快排加贪心骚过
代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct node
{
    int p,d;
}a[10010];

bool f[10010];

bool cmp(node a,node b)
{
    if(a.p==b.p)
    {
        return a.d<b.d;
    }
    else return a.p>b.p;
}

int main()
{
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n)
    {
        memset(f,false,sizeof(f));
        for(int i=0;i<n;i++)
        {
            cin>>a[i].p>>a[i].d;
        }
        sort(a,a+n,cmp);
        int sum=0;
        for(int i=0;i<n;i++)
        {
            for(int j=a[i].d;j>0;j--)
            {
                if(!f[j])
                {
                    f[j]=true;
                    sum+=a[i].p;
                    break;
                }
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注