[CQOI2012]交换棋子

题目描述

有一个n行m列的黑白棋盘,你每次可以交换两个相邻格子(相邻是指有公共边或公共顶点)中的棋子,最终达到目标状态。要求第i行第j列的格子只能参与mi,j次交换。

输入输出格式 输入格式:

第一行包含两个整数n,m(1<=n, m<=20)。以下n行为初始状态,每行为一个包含m个字符的01串,其中0表示黑色棋子,1表示白色棋子。以下n行为目标状态,格式同初始状态。以下n行每行为一个包含m个0~9数字的字符串,表示每个格子参与交换的次数上限。

输出格式: 输出仅一行,为最小交换总次数。如果无解,输出-1。

输入输出样例 输入样例#1:

3 3 110 000 001 000 110 100 222 222 222

输出样例#1:

4

又是一道恶心的网络流

谢谢Asia dalao的耐心讲解

题意可以简化为:将一个01矩阵的相邻格子经过最少多少次交换能够成为目标矩阵,每个格子都有交换次数的上限

我们可以这样理解:将所有的白(0)格子都想成空的,问黑(1)的格子经过多少次变化后能够成为目标

所以我们先从源点向初始的黑格子连一条流量为1,费用为0的边

然后我们再从目标的黑格子向汇点连一条流量为1,费用为0的边

说明有多少的黑格子需要等待交换

然后我们把每个格点拆成三个

我们暂且叫它们 入点,原点,出点

因为每次交换都需要消耗两个格子的交换次数各一次,并且从一个格点经过多次交换后到达的另一格点所经过的格子,除了交换的起点和终点都交换了两次

所以我们将每个格点的交换次数/2,具体连法是 : 入点 -> 原点 -> 出点 , 流量都为交换次数/2

这样从源点连向原点就可以实现从一个格点经过多次交换后到达的另一格点所经过的格子,除了交换的起点和终点都交换了两次。

然而这样还有问题 :

如果一个格点的初始情况与最终情况相同,这样分配流量是显然合理的 ,但如果初始颜色与最终颜色不同,那应该怎么解决呢 ?

(我们已经默认了移动黑点))所以如果一个点的初始点是黑点,最终颜色是白色,那么它就会多流出去一次,那么这样我们就将 原点-> 出点 的流量改为(tim[i][j]+1)/2.

反之,就将入点->原点的流量改为(tim[i][j]+1)/2

最后将每个点的出点和相邻点的入点连一条流量为inf,费用为1的边就好辣

哦,对,还有,如果结果为0就说明不能完成,那就输出-1

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<iostream>
const int M = 25 ;
const int N = 2005 ;
const int inf = 1e8 ;
const int dx[8]={-1,-1,-1,0,1,1,1,0};
const int dy[8]={1,0,-1,-1,-1,0,1,1};
using namespace std;
inline int read(){
	char c=getchar(); int x=0,w=1;
	while(c>'9'||c<'0'){if(c=='-')  w=-1 ;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar(); }
    return x*w;
}
struct E{
	int nex,to,dis,cost;
}edge[N<<8];
int hea[N],num=1;
inline void ins(int from,int to,int dis,int cost){
	edge[++num].nex=hea[from];
	edge[num].to=to;
	edge[num].dis=dis;
	edge[num].cost=cost;
	hea[from]=num;
}
inline void add_edge(int from,int to,int dis,int cost){
	ins(from,to,dis,cost);
	ins(to,from,0,-cost);
}
int n,m,e,st[M][M],End[M][M],tim[M][M],p[M][M];
int Ans,s,t;
int d[N];
bool vis[N],exist[N];
inline bool bfs(){
	queue<int>q; q.push(t);
	memset(d,127/3,sizeof(d)); d[t]=0;
	memset(exist,false,sizeof(exist)); exist[t]=true;
	while(!q.empty()){
		int u=q.front(); q.pop(); exist[u]=false;
		for(int i=hea[u];i;i=edge[i].nex){
			int  v=edge[i].to;
			if(edge[i^1].dis&&d[v]>d[u]-edge[i].cost){
				d[v]=d[u]-edge[i].cost;
				if(!exist[v]){
					q.push(v);
					exist[v]=true;
				}
			}
		}
	}
	return d[s]<inf;
}
int Dfs(int u,int dis){
	vis[u]=1;
	if(u==t||!dis) return dis;
	int sum=0;
	for(int i=hea[u];i;i=edge[i].nex){
		int v=edge[i].to;
		if(!vis[v]&&edge[i].dis&&d[v]==d[u]-edge[i].cost){
			int  diss=Dfs(v,min(edge[i].dis,dis));
			edge[i].dis-=diss;
		    edge[i^1].dis+=diss;
		    sum+=diss;
		    dis-=diss;
		    if(!dis) return sum;
		}
	}
	return sum;
}
inline void mcmf(){
	while(bfs()){
		vis[t]=1;
		while(vis[t]){
			memset(vis,0,sizeof(vis));
			int temp=Dfs(s,inf);
			Ans+=d[s]*temp;
		}
	}
}
char w[105];
int main(){
	n=read(); m=read();
	e=n*m;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	    p[i][j]=(i-1)*m+j;
	s=0,t=n*m*3+5;
	for(int i=1;i<=n;i++){
		scanf("%s",w+1);
		for(int j=1;j<=m;j++)
		  st[i][j]=w[j]-'0';
	}
	for(int i=1;i<=n;i++){
		scanf("%s",w+1);
		for(int j=1;j<=m;j++)
		  End[i][j]=w[j]-'0';
	}
	for(int i=1;i<=n;i++){
	    scanf("%s",w+1);
		for(int j=1;j<=m;j++)
		  tim[i][j]=w[j]-'0';
	}
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++){
	  	if(st[i][j])
		  add_edge(s,p[i][j],1,0);
	  }
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++){
		if(End[i][j])
		  add_edge(p[i][j],t,1,0);
	  }
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++){
	  	if((st[i][j]^End[i][j])==0){
	  		add_edge(p[i][j]+e,p[i][j],tim[i][j]/2,0);
	  		add_edge(p[i][j],p[i][j]+e*2,tim[i][j]/2,0);
		}
		else{
			if(st[i][j]){
				add_edge(p[i][j]+e,p[i][j],tim[i][j]/2,0);
				add_edge(p[i][j],p[i][j]+e*2,(tim[i][j]+1)/2,0);
			}
			else{
				add_edge(p[i][j]+e,p[i][j],(tim[i][j]+1)/2,0);
				add_edge(p[i][j],p[i][j]+e*2,tim[i][j]/2,0);
			}
		}
	  }
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	    for(int k=0;k<8;k++){
	    	int x=i+dx[k],y=j+dy[k];
	    	if(x>=1&&x<=n&&y>=1&&y<=m)
	    	  add_edge(p[i][j]+e*2,p[x][y]+e,inf,1);
		}
	mcmf();
	printf("%d\n",Ans==0 ? -1 : Ans);
	return 0;
}