有一个n行m列的黑白棋盘，你每次可以交换两个相邻格子（相邻是指有公共边或公共顶点）中的棋子，最终达到目标状态。要求第i行第j列的格子只能参与mi,j次交换。
第一行包含两个整数n，m（1<=n, m<=20）。以下n行为初始状态，每行为一个包含m个字符的01串，其中0表示黑色棋子，1表示白色棋子。以下n行为目标状态，格式同初始状态。以下n行每行为一个包含m个0~9数字的字符串，表示每个格子参与交换的次数上限。
输出仅一行，为最小交换总次数。如果无解，输出-1。
3 3
110
000
001
000
110
100
222
222
222
4
首先把题目说的不清楚的地方澄清一下：“第i行第j列的格子只能参与mi,j次交换”所说第i行第j列的棋子指的是每次交换后位于第i行第j列这个位置的棋子，可以是多个，而不是指最原始状态中第i行第j列那个特定的棋子。
很容易发现，我们可以只考虑白色棋子，只要它们都移动到目标状态，剩下的黑棋子也都到目标状态了。 不停地交换听起来好像比较棘手，但其实白棋子只有和身边的黑棋子交换位置才有用。 所以我们就是要给每个白棋子规划一条线路，让它们从原始位置变到目标位置。
很容易想到按原图建图，拆点~ 但有个问题，若某个白格子经过某个格子，那么这个格子会被该白格子交换两次；而白格子原位置与目标位置只会被该白格子交换一次。 于是有一个更高级的拆点：一个点拆成三个！(id1,id2,id3) id1到id2限制其他点与这个点交换的次数，id2到id3限制这个点与其他点交换的次数（即一个是进入的流量，一个是出去的流量）
建图，分类讨论。
对于原状态和目标状态均为黑的格子。 id1到id3连容量为cap/2，费用为1的边对于原状态为白，目标状态为黑的格子。 S到id2连容量为1，费用为0的边 id1到id2连容量为cap/2，费用为1的边 id2到id3连容量为(cap+1)/2，费用为1的边对于原状态为黑，目标状态为白的格子。 id2到T连容量为1，费用为0的边 id1到id2连容量为(cap+1)/2，费用为1的边 id2到id3连容量为cap/2，费用为1的边对于原状态和目标状态均为白的格子。 S到id2连容量为1，费用为0的边 id2到T连容量为1，费用为0的边 id1到id2连容量为cap/2，费用为1的边 id2到id3连容量为cap/2，费用为1的边之后向八连通的格子连边。 注意是某格子的id1连向八连通格子的id3，然后八连通的id1连向这个格子的id3
。。。还是有点复杂的。 接下来就跑个最小费用最大流，看流量是否为总白格子数。 若不是，则输出-1，否则答案为 最小费用/2
注意细节： 1.某些边的容量为(cap+1)/2，容易想错写成cap/2 2.数组要开够！！
#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #define INF 1000000000 using namespace std; const int N = 405; const int M = 1205; struct node{ int v,f,c; node *next,*rev; }pool[N*40],*h[M],*pree[M]; /**/ int cnt; void addedge(int u,int v,int f,int c){ node *p=&pool[++cnt],*q=&pool[++cnt]; p->v=v;p->next=h[u];h[u]=p; p->f=f;p->c=c;p->rev=q; q->v=u;q->next=h[v];h[v]=q; q->f=0;q->c=-c;q->rev=p; } int S,T; int d[M],vis[M],pre[M]; queue<int> que; bool spfa(){ int u,v; while(!que.empty()) que.pop(); for(int i=S;i<=T;i++) d[i]=INF; d[S]=0; vis[S]=1; que.push(S); while(!que.empty()){ u=que.front(); que.pop(); vis[u]=0; for(node *p=h[u];p;p=p->next) if(p->f && d[v=p->v]>d[u]+p->c){ d[v]=d[u]+p->c; pre[v]=u; pree[v]=p; if(!vis[v]){ vis[v]=1; que.push(v); } } } return d[T]!=INF; } void MCMF(int &f,int &c){ f=0; c=0; int u,w; while(spfa()){ u=T; w=INF; while(u!=S){ w=min(w,pree[u]->f); u=pre[u]; } f+=w; c+=d[T]*w; u=T; while(u!=S){ pree[u]->f-=w; pree[u]->rev->f+=w; u=pre[u]; } } } int n,m; char a[23][23],b[23][23],ch[23][23]; int dre[8][2]={-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1}; int main() { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%s",a[i]); for(int i=0;i<n;i++) scanf("%s",b[i]); for(int i=0;i<n;i++) scanf("%s",ch[i]); int w=n*m,id1,id2,id3,tot=0; S=0; T=w*3+1; for(int i=0;i<n;i++) for(int j=0;j<m;j++){ id1=i*m+j+1; id2=id1+w; id3=id2+w; if(a[i][j]=='0' && b[i][j]=='0') addedge(id1,id3,(ch[i][j]-'0')/2,2); else if(a[i][j]=='1' && b[i][j]=='0'){ tot++; addedge(S,id2,1,0); addedge(id1,id2,(ch[i][j]-'0')/2,1); addedge(id2,id3,(ch[i][j]-'0'+1)/2,1); /**/ } else if(a[i][j]=='0' && b[i][j]=='1'){ addedge(id2,T,1,0); addedge(id1,id2,(ch[i][j]-'0'+1)/2,1); /**/ addedge(id2,id3,(ch[i][j]-'0')/2,1); } else{ tot++; addedge(S,id2,1,0); addedge(id2,T,1,0); addedge(id1,id2,(ch[i][j]-'0')/2,1); addedge(id2,id3,(ch[i][j]-'0')/2,1); } for(int k=0;k<8;k++){ int x=i+dre[k][0],y=j+dre[k][1]; if(x>=0 && x<n && y>=0 && y<m){ addedge(id3,x*m+y+1,INF,0); addedge(x*m+y+1+2*w,id1,INF,0); } } } int f,c; MCMF(f,c); if(f<tot) printf("-1\n"); else printf("%d",c/2); return 0; }转载于:https://www.cnblogs.com/lindalee/p/8598122.html
相关资源：数据结构—成绩单生成器