T1.relation(亲戚)

题意:给定一些人是亲戚的关系,并询问某两人是不是亲戚
分析:利用并查集维护每个亲戚集合。

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 5001

using namespace std;

int fa[MX];
int n,m,p;

int findfa(int x){return fa[x]==x?x:(fa[x]=findfa(fa[x]));}

void comb(int a,int b){fa[findfa(a)]=findfa(b);}

int main()
{
    freopen("relation.in","r",stdin);
    freopen("relation.out","w",stdout);
    int a,b;
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        comb(a,b);
    }
    for(int i=1;i<=p;i++)
    {
        scanf("%d%d",&a,&b);
        if(findfa(a)==findfa(b))printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

T2.gangs(黑社会团伙)

题意:我的朋友的朋友是我的朋友,我的敌人的敌人是我的朋友。现在给出一些人的关系,求最多存在多少组朋友(单独的人也是一组朋友)
思路:这道题有多种理解,按照“朋友的敌人是敌人,敌人的朋友也是敌人”的理解,我们可以用带权并查集做。

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 5001

using namespace std;

int fa[MX],dis[MX];
int kind[MX];
int n,m;

int findfa(int x)
{
    if(fa[x]==x)return x;
    else
    {
        findfa(fa[x]);
        dis[x]+=dis[fa[x]];
        fa[x]=fa[fa[x]];
        return fa[x];
    }
}

void frid(int a,int b)
{
    int f1,f2;
    f1=findfa(a),f2=findfa(b);
    if(f1==f2)return;
    fa[f1]=f2;
    if(dis[a]%2==dis[b]%2)dis[f1]=0;
    else dis[f1]=1;
}

void enem(int a,int b)
{
    int f1,f2;
    f1=findfa(a),f2=findfa(b);
    if(f1==f2)return;
    fa[f1]=f2;
    if(dis[a]%2!=dis[b]%2)dis[f1]=0;
    else dis[f1]=1;
}

int main()
{
    freopen("gangs.in","r",stdin);
    freopen("gangs.out","w",stdout);
    char op;
    int a,b;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        op=getchar();
        while(op!='E'&&op!='F')op=getchar();
        scanf("%d%d",&a,&b);
        if(op=='E')enem(a,b);
        else frid(a,b);
    }
    for(int i=1;i<=n;i++)
    {
        findfa(i);
        if(kind[fa[i]]==0&&dis[i]%2==0)kind[fa[i]]++;
        if(kind[fa[i]]==1&&dis[i]%2==1)kind[fa[i]]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(kind[fa[i]]==0&&dis[i]%2==0)kind[fa[i]]++;
        if(kind[fa[i]]==1&&dis[i]%2==1)kind[fa[i]]++;
    }
    int tot=0;
    for(int i=1;i<=n;i++)tot+=kind[i];
    printf("%d\n",tot);
    return 0;
}

T3.filling(矩形填补)

题意:平面上的边平行于坐标轴的矩形,如果三个角上有黑点,那么将第四个角也染成黑点。现在给出一开始的黑点,求最后平面上有多少个点。
分析:注意到最后形成的点集一定为几个互相没有公共点的矩形的并(这里的矩形包括33,34等的内部有多个点的矩形)。为什么会这样呢?把每个点所在的横线和竖线画出来自然就清楚了。经过分析,我们得出以下结论:
1.一个点可以将它所在的横线和竖线连接起来。
2.两个已经被连接起来的线的交点一定是一个黑点。
所以我们只需要维护有多少横线竖线被点连接在一起。这个利用并查集可以轻松完成。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 1000010

using namespace std;

typedef struct sfga
{
    int x,y;
    int sx,sy;
}point;

int fa[MX],mx,my;
int ynum[MX],xnum[MX];
char vis[MX];
point src[MX/2];
int n;

int cmpx(point a,point b){if(a.x==b.x)return a.y<b.y;else return a.x<b.x;}

int cmpy(point a,point b){if(a.y==b.y)return a.x<b.x;else return a.y<b.y;}

int findfa(int x){return x==fa[x]?x:(fa[x]=findfa(fa[x]));}

void comb(int a,int b)
{
    if(findfa(a)==findfa(b))return;
    xnum[findfa(b)]+=xnum[findfa(a)];
    ynum[findfa(b)]+=ynum[findfa(a)];
    fa[findfa(a)]=findfa(b);
}

int main()
{
    freopen("filling.in","r",stdin);
    freopen("filling.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&src[i].x,&src[i].y);
    sort(src+1,src+n+1,cmpx);
    for(int now=0,i=1;i<=n;i++)
    {
        if(src[i].x!=src[i-1].x||i==1)now++;
        src[i].sx=now;
        mx=now;
    }
    sort(src+1,src+n+1,cmpy);
    for(int now=0,i=1;i<=n;i++)
    {
        if(src[i].y!=src[i-1].y||i==1)now++;
        src[i].sy=now;
        my=now;
    }
    for(int i=1;i<=mx+my;i++)fa[i]=i;
    for(int i=1;i<=mx;i++)xnum[i]=1;
    for(int i=mx+1;i<=mx+my;i++)ynum[i]=1;
    for(int i=1;i<=n;i++)comb(src[i].sx,src[i].sy+mx);
    long long ans=0;
    for(int i=1;i<=mx+my;i++)
    {
        if(vis[findfa(i)])continue;
        ans+=(long long)xnum[fa[i]]*(long long)ynum[fa[i]];
        vis[fa[i]]=1;
    }
    cout<<ans<<endl;
    return 0;
}

T4.game(格子游戏)

题意:两位大爷在n*n的棋盘上连线,两人轮流连接一条棋盘上的单位长度的边,给出每一步他们连接的起始点坐标和连接方向,求谁先连出一个环。
分析:并查集维护连通性。


#include <iostream> #include <cstring> #include <cstdio> #define MX 2000010 using namespace std; int fa[MX],n,m; int findfa(int x){return (x==fa[x]?x:(fa[x]=findfa(fa[x])));} int comb(int a,int b) { if(findfa(a)==findfa(b))return 1; fa[findfa(a)]=findfa(b); return 0; } int main() { freopen("game.in","r",stdin); freopen("game.out","w",stdout); int x,y; char c; scanf("%d%d",&n,&m); for(int i=1;i<=n*(n+1);i++)fa[i]=i; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); c=getchar(); while(c!='D'&&c!='R')c=getchar(); if(c=='D') { if(comb((x-1)*(n+1)+y,x*(n+1)+y)) { cout<<i<<endl; return 0; } } else { if(comb((x-1)*(n+1)+y,(x-1)*(n+1)+y+1)) { cout<<i<<endl; return 0; } } } cout<<-1<<endl; return 0; }

T5.lyp(打怪兽)

题意:有n个怪兽,不停给出如下两个操作:
1 a b c:告诉你a怪兽比b怪兽强c
2 a b:询问a和b谁强。如果一样强或不知道,就输出0
分析:带权并查集维护每个怪兽比所在根节点的怪兽强多少。

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 31000

using namespace std;

int fa[MX],dis[MX];
int n,q;

int findfa(int x)
{
    if(fa[x]==x)return x;
    else
    {
        findfa(fa[x]);
        dis[x]+=dis[fa[x]];
        fa[x]=fa[fa[x]];
        return fa[x];
    }
}

void big(int a,int b,int c)
{
    int f1=findfa(a),f2=findfa(b);
    if(f1==f2)return;
    fa[f1]=f2;
    dis[f1]=dis[b]-dis[a]+c;
}

int query(int a,int b)
{
    int f1=findfa(a),f2=findfa(b);
    if(f1!=f2)return 0;
    if(dis[a]==dis[b])return 0;
    return (dis[a]>dis[b]?a:b);
}

int main()
{
    freopen("lyp.in","r",stdin);
    freopen("lyp.out","w",stdout);
    int op,a,b,c;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d",&a,&b,&c);
            big(a,b,c);
        }
        else
        {
            scanf("%d%d",&a,&b);
            printf("%d\n",query(a,b));
        }
    }
    return 0;
}
分类: 所有

发表评论

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

你是机器人吗? =。= *