lp3159 CQOI2012 交换棋子

首先是一个常见套路:将棋子的交换等价为棋子的移动——这很重要。我们不妨把交换看做黑子的移动。
那么我们考虑这个问题的弱化版:假设每个格子的移动次数没有限制,该怎么做。
很显然将每个格子拆成两个点,然后每个右点向相邻的左点连边,跑最大流即可。
对于一个黑子的移动,我们发现,如果一个格子是这个黑子中途经过的点,那么这个格子必然会消耗两次交换次数。
故而,我们给从左点到右点的边设置一个容量上限,其值为交换次数上限的一半。
但是这么做的话我们发现了一个问题:倘若一个点起始状态和结束状态不一样,这个模型是无法有效描述结果的。
这是因为,如果一个点的起始状态和结束状态不一样,那么它通过的次数必然是奇数。
我们考虑这样拆点:将每个点拆成左,中,右三个点。然后,将每个点的右点向它的所有相邻点的左点连边,流量1,费用0。表示某个棋子走向了它的另一个相邻的棋子。
从中点向右点连一条边,表示这个点移出去的次数。显然,如果最终情况是白的而初始情况是黑的,这个点应该会多移出去一次。
从左点向中点连一条边,表示这个点移进来的次数。显然,如果最终情况是黑的而初始情况是白的,这个点应该会多移进来一次。
我们考虑这个「多移进来」和「多移出去」对这个点可以参与的交换次数的影响。
假若限定次数是偶数,那么多出来的这一次移动将使得这个点能参与的交换次数少一次;倘若限定次数是奇数,那么多出来的这一次移动将不影响这个点能参与的交换次数。
所以,我们可以用形如\(\lfloor \frac{limit+[end>begin]}{2} \rfloor \)和\(\lfloor \frac{limit+[begin>end]}{2} \rfloor \)的式子来描述这两条边的流量。
然后,对于题目要求的最小交换次数,我们考虑将原来就存在的连边加上费用。这样就满足了题目的要求。

#include<iostream>
#include<cstdio>
#include<queue>

const int dx[8]={-1,-1,-1,0,0,1,1,1};
const int dy[8]={1,0,-1,1,-1,1,0,-1};

const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int c;
	int nxt;
}e[200005];
int h[1205],et=-1;
inline void Eadd(int U,int V,int W,int C){
	e[++et]=(ee){V,W,C,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int C){
	Eadd(U,V,W,C);
	Eadd(V,U,0,-C);
}

int n,m,s,t,vis[1205],dis[1205],val[1205],fa[1205],nw[1205];

std::queue<int> q;
inline bool SPFA(){
	for(int i=1;i<=t;++i){
		vis[i]=0,dis[i]=INF,val[i]=INF;
	}
	vis[s]=1,dis[s]=0,fa[t]=-1;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		vis[p]=0;
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
				dis[e[i].v]=dis[p]+e[i].c;
				fa[e[i].v]=p;
				nw[e[i].v]=i;
				val[e[i].v]=Min(e[i].w,val[p]);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
	}
	return fa[t]!=-1;
}
int answ=0,ansc=0;
inline void zkw(){
	int p;
	while(SPFA()){
		p=t;
		answ+=val[t];
		ansc+=val[t]*dis[t];
		while(p!=s){
			e[nw[p]].w-=val[t];
			e[nw[p]^1].w+=val[t];
			p=fa[p];
		}
	}
}

char begin[25][25],end[25][25],limit[25][25];
inline int calc(int X,int Y,int T){
	return T*n*m+(X-1)*m+Y;
}

void init(){
	scanf("%d%d",&n,&m);
	s=3*n*m+1,t=3*n*m+2;
	int cnt=0;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	for(int i=1;i<=n;++i){
		std::cin>>begin[i]+1;
	}
	for(int i=1;i<=n;++i){
		std::cin>>end[i]+1;
	}
	for(int i=1;i<=n;++i){
		std::cin>>limit[i]+1;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(begin[i][j]=='1'){
				++cnt;
				add(s,calc(i,j,1),1,0);
			}
			add(calc(i,j,1),calc(i,j,2),(limit[i][j]-'0'+(int)(begin[i][j]>end[i][j]))>>1,1);
			if(end[i][j]=='1'){
				add(calc(i,j,1),t,1,0);
			}
			add(calc(i,j,0),calc(i,j,1),(limit[i][j]-'0'+(int)(end[i][j]>begin[i][j]))>>1,1);
			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){
					//n,m!!!
					add(calc(i,j,2),calc(x,y,0),INF,0);
				}
			}
		}
	}
	zkw();
	printf("%d\n",(answ==cnt?ansc:-1)>>1);
}

int main(){
	init();
	return 0;
}