题解：P6517 [CEOI2010 day1] alliances

#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;
}