题解：P6517 [CEOI2010 day1] alliances

思路

考虑拆点：elves 就是一个单点，human 拆成两个点一个向上下连边，一个向左右连边，drawves 拆成五个点，中间一个向周围四个连边，hobbits 就是四个点。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 25005
using namespace std;
int m,n,tot,cnt,fst[N],pnt[N],nxt[N],a[75][75],p[75][75][4],pre[N],blg[N];
bool bo[N],mp[215][215];
void add(int x,int y,bool z)
{
    if(!z)
    {
        swap(x,y);
    }
    pnt[++tot]=y;
    nxt[tot]=fst[x];
    fst[x]=tot;
}
bool dfs(int x)
{
    int i,y;
    for(i=fst[x];i;i=nxt[i])
    {
        y=pnt[i];
        if(bo[y])
        {
            bo[y]=0;
            if(!pre[y]||dfs(pre[y]))
            {
                pre[y]=x;
                return 1;
            }
        }
    }
    return 0;
}
void work(int x,int y)
{
    if(!x||!y)
    {
        return;
    }
    if(x>y)
    {
        swap(x,y);
    }
    int v=(x-1)%n+1,u=(x-v)/n+1;
    u=u*3-1;
    v=v*3-1;
    if(x+n==y) 
    {
        mp[u+1][v]=mp[u+2][v]=1; 
    }
    else
    {
        mp[u][v+1]=mp[u][v+2]=1;
    }
}
int main()
{
    scanf("%d%d",&m,&n);
    int i,j,k;
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
            if(!a[i][j])
            {
                continue;
            }
            if(a[i][j]==1)
            {
                p[i][j][0]=p[i][j][1]=p[i][j][2]=p[i][j][3]=++cnt;
            }
            else
            {
                if(a[i][j]==2)
                {
                    p[i][j][0]=p[i][j][1]=++cnt;
                    p[i][j][2]=p[i][j][3]=++cnt;
                } 
                else
                {
                    for(k=0;k<4;k++)
                    {
                        p[i][j][k]=++cnt;
                    }
                    if(a[i][j]==3)
                    {
                        cnt++;
                        for(k=0;k<4;k++)
                        {
                            add(p[i][j][k],cnt,i+j&1);
                        }
                    }                       
                }
            }
        }
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            for(k=0;k<4;k++) blg[p[i][j][k]]=(i-1)*n+j;
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++) 
        {
            if(a[i][j])
            {
                if(a[i+1][j]) add(p[i][j][1],p[i+1][j][0],i+j&1);
                if(a[i][j+1]) add(p[i][j][3],p[i][j+1][2],i+j&1);
            }       
        }
    int ans=0;
    for(i=1;i<=cnt;i++)
    {
        memset(bo,1,sizeof(bo));
        if(dfs(i)) ans++;
    }
    if((ans<<1)<cnt)
    {
        puts("Impossible!");
        return 0;
    }
    for(i=1;i<=cnt;i++)
        if(pre[i]) work(blg[pre[i]],blg[i]);
    for(i=1;i<=3*m;puts(""),i++)
        for(j=1; j<=3*n;j++)
            if(i%3==2&&j%3==2&&a[i/3+1][j/3+1]) putchar('O');
            else putchar(mp[i][j]?'X':'.');
    return 0;
}