@TryMyEdge 2017-02-11T14:32:24.000000Z 字数 5980 阅读 906

专题四(并查集、生成树)

题解

A How Many Tables

题目大意：

    有N(1<=N<=1000)个朋友，M(1<=M<=1000)条关系，第i条关系表示ai和bi是朋友(1<=ai，bi<=N，ai!=bi)。朋友(包括直接和间接)可以坐在一桌吃饭。问需要多少张桌子。
    T(1<=T<=25)组数据。

解题思路：

    并查集裸题，把每个关系的两个端点所在的并查集合并，最后看有多少个并查集就行了。
    N和M都是1000，优不优化无所谓。。。
    时间复杂度o(T*(N+M))，空间复杂度o(N)。

AC代码：

#include<iostream>
#include<cstdio>
#define pq priority_queue
#define Pi acos(-1.0)
using namespace std;
#define MOD 1000000007
int root[1005];
int findr(int x)
{
    if(root[x]==x)
        return x;
    else
        return root[x]=findr(root[x]);
}
int main()
{
    int T,n,m,a,b,ans;
    cin>>T;
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            root[i]=i;
        while(m--)
        {
            scanf("%d%d",&a,&b);
            a=findr(a);
            b=findr(b);
            root[a]=b;
        }
        ans=0;
        for(int i=1;i<=n;i++)
        {
            if(root[i]==i)
                ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

B Corporative Network

题目大意：

    有N(5<=N<=20000)个点，M(M<=200000)个操作，M不直接给出。
    操作分三种：
    (1)I x y，表示x(保证x之前没有父亲)的父亲变为y
    (2)E x，询问x到根的距离(儿子到父亲的距离为两个点编号差的绝对值)
    (3)O，表示该组数据结束
    T组数据。

解题思路：

    维护每个点到当前根的距离，初始状态每个点的根为自己，距离为0，如果遇到操作(1)则更将x的根改为y，距离改为x和y的差的绝对值。查询的时候再修改根的过程中同时修改这条链上每个点和根的距离。
    压缩路径。
    时间复杂度o(N+M)，空间复杂度o(N)。

AC代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define pq priority_queue
#define Pi acos(-1.0)
using namespace std;
#define MOD 1000000007
int root[20005];
int num[20005];
int findr(int x)
{
    int y;
    if(root[x]==x)
        return x;
    else
    {
        y=root[x];
        root[x]=findr(root[x]);
        num[x]+=num[y];
        return root[x];
    }
}
int main()
{
    int T,n,m,a,b,ans;
    char c[6];
    cin>>T;
    while(T--)
    {
        scanf("%d%d",&n);
        for(int i=1;i<=n;i++)
        {
            root[i]=i;
            num[i]=0;
        }
        while(scanf("%s",c),c[0]!='O')
        {
            if(c[0]=='I')
            {
                scanf("%d%d",&a,&b);
                root[a]=b;
                num[a]=abs(a-b)%1000;
            }
            else
            {
                scanf("%d",&a);
                findr(a);
                printf("%d\n",num[a]);
            }
        }
    }
    return 0;
}

C 卿学姐与诡异村庄

题目大意：

    一个村庄里有N(1<=N<=100000)个人，其中不是好人就是坏人。好人只会说真话，坏人只会说假话。每个人会指认一名其他人是好人或者坏人。问是否存在一种分类满足所有的指控。

解题思路：

    每个人有两种可能性：好人或者坏人。
    若A说B是好人，则A如果说假话，A和B同为坏人，若A说真话，则A和B同为好人。同理，若A说B是坏人，则A和B一定一好一坏。所以对于这每条信息的两种情况，分别把对应的两个可能性所处的并查集合并。最后检查是否有某个人为好人和为坏人的可能性处于一个并查集，也就是某人既是好人又是坏人，判断是否有分类符合要求。
    时间复杂度o(N)，空间复杂度o(N)。

AC代码：

#include<iostream>
#include<cstdio>
#include<queue>
#define pq priority_queue
#define Pi acos(-1.0)
using namespace std;
#define MOD 1000000007
int root[200005];
int findr(int x)
{
    if(root[x]==x)
        return x;
    else
        return root[x]=findr(root[x]);
}
int main()
{
    int n,a,b,c,d;
    bool ans;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        root[i]=i;
        root[i+100001]=i+100001;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&c,&d);
        if(d==1)
        {
            a=findr(i);
            b=findr(c);
            root[a]=b;
            a=findr(i+100001);
            b=findr(c+100001);
            root[a]=b;
        }
        else
        {
            a=findr(i);
            b=findr(c+100001);
            root[a]=b;
            a=findr(i+100001);
            b=findr(c);
            root[a]=b;
        }
    }
    ans=0;
    for(int i=1;i<=n;i++)
         ans|=findr(i)==findr(i+100001);
    if(ans)
        printf("One face meng bi\n");
    else
        printf("Time to show my power\n");
    return 0;
}

D 食物链

题目大意：

    动物分ABC三种，A吃B、B吃C、C吃A。有N(1<=N<=50000)个动物，K(0<=K<=100000)句话，每句话描述了某两个动物间的关系是属于同一种类或者前者吃后者。一句话如果提到了这N个动物之外的动物、描述自己吃自己或者与之前的话矛盾，这句话就是假话，否则就是真话。问假话的总数。

解题思路：

    和C题的思路有些类似。每种动物有ABC三种可能性。如果用←→把共存的可能性连接起来，那么我们就可以用x.A←→y.A、x.B←→y.B、x.C←→y.C表示x和y属于同一种类，用x.A←→y.B，x.B←→y.C、x.C←→y.A表示x吃y。对于每一句话，先查询是否存在某个与这句话的可能性属于同一个并查集，不存在的话就把对应的可能性所属的并查集合并。
    时间复杂度o(k+N)，空间复杂度o(N)。

AC代码：

#include<iostream>
#include<cstdio>
#define pq priority_queue
#define Pi acos(-1.0)
using namespace std;
#define MOD 1000000007
int root[150010];
int findr(int x)
{
    if(root[x]==x)
        return x;
    else
        return root[x]=findr(root[x]);
}
int main()
{
    int n,a,b,c,d,e,f,flag;
    int ans=0,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        root[i]=i;
        root[i+50001]=i+50001;
        root[i+100002]=i+100002;
    }
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d%d",&flag,&a,&b);
        if(a>n || b>n)
            ans++;
        else
        {
            c=findr(a+50001);
            d=findr(b+50001);
            e=findr(a+100002);
            f=findr(b+100002);
            a=findr(a);
            b=findr(b);
            if(flag==1)
            {
                if(a==d || a==f)
                    ans++;
                else
                {
                    root[a]=b;
                    root[c]=d;
                    root[e]=f;
                }
            }
            else
            {
                if(a==b || a==f)
                    ans++;
                else
                {
                    root[a]=d;
                    root[c]=f;
                    root[e]=b;
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

E Dark roads

题目大意：

    有m(1<=m<=200000)个点，由n(m-1<=n<=200000)条无向边连接，第i条边有一个权值zi，原图保证联通。在保证图联通的情况下，删去其中一部分边，求被删去的边的总权值最大为多少。
    多组数据。保证所有边的总权值不超过2^31。

解题思路：

    最小生成树裸题。
    如果当前图不是一颗树，那么一定有环，环上至少一条边可以删去。于是最后删完剩下的图一定是原图的一颗生成树。于是问题就转化为求总权值最小的生成树，再用所有边的总权值减去最小生成树的总权值。最小生成树的方法求prim或者用kruskal都行，我这里用的是kruskal。
    小细节：注意点的编号是从0到m-1。
    时间复杂度o(n*logn)，空间复杂度o(n+m)。

AC代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define pq priority_queue
#define Pi acos(-1.0)
using namespace std;
#define MOD 1000000007
struct Edge
{
    int u,v;
    long long l;
    friend bool operator <(Edge a,Edge b)
    {
        return a.l<b.l;
    }
}e[200005];
int root[200005];
int findr(int x)
{
    if(root[x]==x)
        return x;
    else
        return root[x]=findr(root[x]);
}
int main()
{
    int n,m;
    long long ans;
    while(cin>>n>>m,n||m)
    {
        ans=0;
        for(int i=0;i<n;i++)
            root[i]=i;
        for(int i=0;i<m;i++)
            scanf("%d%d%lld",&e[i].u,&e[i].v,&e[i].l);
        sort(e,e+m);
        for(int i=0;i<m;i++)
        {
            if(findr(e[i].u)==findr(e[i].v))
                ans+=e[i].l;
            else
                root[findr(e[i].u)]=findr(e[i].v);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

F Design Tutorial: Inverse the Problem

题目大意：

    给出一个n*n(1<=n<=2000)的矩阵D，Dij(0<=Dij<=10^9)表示点i和点j的最短距离，问是否有一个由n个点，n-1条正整数权值边组成的树，满足这个邻接矩阵。

解题思路：

    如果D是某个树对应的邻接矩阵，因为每条边的权值都是正的，那么这树上的n-1条边也一定表示在邻接矩阵中，于是我们用这n*n条边(实际上只要取n*(n-1)/2条)进行最小生成树，然后根据生成树处理出另一个邻接矩阵与原矩阵进行比对看是不是一样就行了。
    我对代码进行了一些修改，反正要跑出n*n个点对的距离，n^2的复杂度是不可避免的，所以我干脆在合并点集的时候 就将两个点集中点配对的距离通过新加的这条边进行计算，于是就不需要并查集了，可以直接维护点的根。
    小细节：当答案为no的时候，有可能会出现某些点对之间的距离因为由几条边的权值相加导致爆int。
    时间复杂度o(n^2*log(n^2))，空间复杂度o(n^2)。

AC代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define pq priority_queue
#define Pi acos(-1.0)
using namespace std;
#define MOD 1000000007
struct Edge
{
    int u,v;
    long long l;
    friend bool operator <(Edge a,Edge b)
    {
        return a.l<b.l;
    }
}e[4000005],temp;
int root[2005];
int v[2005][2005],lens[2005];
long long ans[2005][2005],dis[2005][2005];
int main()
{
    int n,cnt=0,a,b,c,d;
    bool flag=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        lens[i]=1;
        v[i][0]=i;
        root[i]=i;
        for(int j=1;j<=n;j++)
        {
            scanf("%lld",&dis[i][j]);
            if(i!=j)
            {
                if(!dis[i][j])
                    flag=1;
                if(i<j)
                {
                    temp.u=i;
                    temp.v=j;
                    temp.l=dis[i][j];
                    e[cnt++]=temp;
                }
            }
            else
            {
                if(dis[i][j])
                    flag=1;
            }
        }
    }
    sort(e,e+cnt);
    for(int t=0;t<cnt;t++)
    {
        if(root[e[t].u]!=root[e[t].v])
        {
            a=root[e[t].u];
            b=root[e[t].v];
            c=lens[a];
            d=lens[b];
            for(int i=0;i<c;i++)
            {
                for(int j=0;j<d;j++)
                {
                    ans[v[a][i]][v[b][j]]=ans[v[b][j]][v[a][i]]=ans[v[a][i]][e[t].u]+e[t].l+ans[e[t].v][v[b][j]];
                    if(ans[v[a][i]][v[b][j]]!=dis[v[a][i]][v[b][j]] || ans[v[b][j]][v[a][i]]!=dis[v[b][j]][v[a][i]])
                        flag=1;
                }
                root[v[a][i]]=b;
                v[b][lens[b]++]=v[a][i];
            }
        }
    }
    if(flag)
        printf("NO\n");
    else
        printf("YES\n");
    return 0;
}

专题四(并查集、生成树)

内容目录