【BZOJ2668】[cqoi2012]交换棋子
Description
有一个n行m列的黑白棋盘，你每次可以交换两个相邻格子（相邻是指有公共边或公共顶点）中的棋子，最终达到目标状态。要求第i行第j列的格子只能参与mi,j次交换。
Input
第一行包含两个整数n，m（1<=n, m<=20）。以下n行为初始状态，每行为一个包含m个字符的01串，其中0表示黑色棋子，1表示白色棋子。以下n行为目标状态，格式同初始状态。以下n行每行为一个包含m个0~9数字的字符串，表示每个格子参与交换的次数上限。
Output
输出仅一行，为最小交换总次数。如果无解，输出-1。
Sample Input
3 3
110
000
001
000
110
100
222
222
222
110
000
001
000
110
100
222
222
222
Sample Output
4
题解：容易想到费用流，从S向原图中所有1连边，新图中所有1向T连边，中间边的费用是1。但是中间的边我们既要限制入度又要限制出度，该怎么连呢？
我们仔细观察发现，如果相邻的两个都是1或都是0肯定不会交换，也就是说我们每次交换都会导致当前点的颜色改变。即如果当前点原图是0新图是0或原图是1新图是1，则该点的入度=出度；如果原图是1新图是0，则入度+1=出度；原图是0新图是1，则入度=出度+1。这样的话解个方程就知道具体的入度和出度限制了，所以我们只需要限制一下入度即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
queue<int> q;
int n,m,ta,tb,S,T,cnt,ans;
char s1[30][30],s2[30][30],s3[30][30];
inline int _(int a,int b) {return (a-1)*m+b;}
inline int __(int a,int b) {return (a-1)*m+b+n*m;}
int to[400010],next[400010],head[1010],cost[400010],flow[400010],dis[1010],pe[1010],pv[1010],inq[1010];
inline void add(int a,int b,int c,int d)
{
to[cnt]=b,cost[cnt]=c,flow[cnt]=d,next[cnt]=head[a],head[a]=cnt++;
to[cnt]=a,cost[cnt]=-c,flow[cnt]=0,next[cnt]=head[b],head[b]=cnt++;
}
inline int bfs()
{
memset(dis,0x3f,sizeof(dis));
dis[S]=0,q.push(S);
int i,u;
while(!q.empty())
{
u=q.front(),q.pop(),inq[u]=0;
for(i=head[u];i!=-1;i=next[i]) if(flow[i]&&dis[to[i]]>dis[u]+cost[i])
{
dis[to[i]]=dis[u]+cost[i],pe[to[i]]=i,pv[to[i]]=u;
if(!inq[to[i]]) inq[to[i]]=1,q.push(to[i]);
}
}
return dis[T]<0x3f3f3f3f;
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m),S=0,T=2*n*m+1;
int i,j,a,b;
for(i=1;i<=n;i++)
{
scanf("%s",s1[i]+1);
for(j=1;j<=m;j++) if(s1[i][j]=='1') ta++,add(S,_(i,j),0,1);
}
for(i=1;i<=n;i++)
{
scanf("%s",s2[i]+1);
for(j=1;j<=m;j++) if(s2[i][j]=='1') tb++,add(_(i,j),T,0,1);
}
if(ta!=tb)
{
puts("-1");
return 0;
}
for(i=1;i<=n;i++)
{
scanf("%s",s3[i]+1);
for(j=1;j<=m;j++)
{
if(s3[i][j]-'0'-s1[i][j]+s2[i][j]<0)
{
puts("-1");
return 0;
}
add(__(i,j),_(i,j),1,(s3[i][j]-'0'-s1[i][j]+s2[i][j])>>1);
for(a=i-1;a<=i+1;a++) for(b=j-1;b<=j+1;b++) if((a!=i||b!=j)&&a&&b&&a<=n&&b<=m)
add(_(i,j),__(a,b),0,1<<30);
}
}
while(bfs())
{
ta--,ans+=dis[T];
for(i=T;i!=S;i=pv[i]) flow[pe[i]]--,flow[pe[i]^1]++;
}
printf("%d",ta?-1:ans);
return 0;
}//1 3 100 001 121