【BZOJ-2668】交换棋子 最小费用最大流

2668: [cqoi2012]交换棋子

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 1055  Solved: 388
[Submit][Status][Discuss]

Description

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

Input

第一行包含两个整数nm(1<=nm<=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

Sample Output

4

HINT

Source

Solution

这是一道建图比较有趣的费用流.

想到用费用流比较容易,很显然,连法必然是S连向原图中的黑点,新图中的黑点连向T,问题在于中间的连边,如何利用容量限制两个点。

自己一开始立马想到拆点,但是是很naive的一拆二,限制容量,但这样并不可以。

实际上这个题需要一个点拆成3个点,我们把点$x$拆成$x_{1},x_{2},x_{3}$,并连出$x_{1}-->x_{2}-->x_{3}$

其中$x_{1}-->x_{2}$表示$x$这个点最多流入的流量,$x_{2}-->x_{3}$表示$x$这个点最多流出的流量。

对于一个点$x$,如果只是原图的黑点,那么限制$<x_{1},x_{2}>:cap=\frac{use[x]}{2};cost=0 ; <x_{2},x_{3}>:cap=\frac{use[x]+1}{2};cost=0$

并且连$S-->x_{2} : cap=1;cost=0$

对于一个点$x$,如果只是新图的黑点,那么限制$<x_{1},x_{2}>:cap=\frac{use[x]+1}{2};cost=0 ; <x_{2},x_{3}>:cap=\frac{use[x]}{2};cost=0$

并且连$x_{2}-->T : cap=1;cost=0$

如果一个点$x$,如果在原图和新图中都是白点或者都是黑点,那么我们限制$<x_{1},x_{2}>:cap=\frac{use[x]}{2};cost=0 ; <x_{2},x_{3}>:cap=\frac{use[x]}{2};cost=0$

对于图中的八连通格两两$x ; y$,连边$x_{3}-->y_{1} :cap=INF ; cost=1$流经此边,表示交换一次。

上述的限制方法,实际上是对网格的每个位置的流量变化进行讨论得到的,因为是一个最值情况,所以很多流入流出限制都无法完全流满。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
#define MAXM 100010
#define MAXN 2000
int N,M,used[][];
char st[][],ed[][],us[][];
struct EdgeNode{int next,to,cap,cost;}edge[MAXM];
int cnt=,head[MAXN];
inline void AddEdge(int u,int v,int w,int c) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].cap=w; edge[cnt].cost=c;}
inline void InsertEdge(int u,int v,int w,int c) {AddEdge(u,v,w,c); AddEdge(v,u,,-c);}
int dis[MAXN],S,T,Cost,Flow;
bool mark[MAXN];
#define INF 0x7fffffff
inline bool SPFA()
{
memset(mark,,sizeof(mark));
for (int i=S; i<=T; i++) dis[i]=INF;
queue<int>q;
q.push(S); dis[S]=; mark[S]=;
while (!q.empty())
{
int now=q.front(); q.pop(); mark[now]=;
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].cap && dis[edge[i].to]>dis[now]+edge[i].cost)
{
dis[edge[i].to]=dis[now]+edge[i].cost;
if (!mark[edge[i].to]) q.push(edge[i].to),mark[edge[i].to]=;
}
}
return dis[T]!=INF;
}
inline int DFS(int loc,int low)
{
mark[loc]=;
if (loc==T) return low;
int used=,w;
for (int i=head[loc]; i; i=edge[i].next)
if (edge[i].cap && !mark[edge[i].to] && dis[edge[i].to]==dis[loc]+edge[i].cost)
{
w=DFS(edge[i].to,min(edge[i].cap,low-used));
edge[i].cap-=w; edge[i^].cap+=w; used+=w; Cost+=w*edge[i].cost;
if (low==used) return used;
}
return used;
}
inline int zkw()
{
int re=;
while (SPFA())
{
mark[T]=;
while (mark[T]) memset(mark,,sizeof(mark)),re+=DFS(S,INF);
}
return re;
}
int id[][][],ID,black,white;
int dx[]={-,-,-,,,,,},dy[]={-,,,-,,-,,};
inline bool check(int x,int y) {return x>= && x<=N && y>= && y<=M;}
void BuildGraph()
{
for (int i=; i<=N; i++)
for (int j=; j<=M; j++)
for (int k=; k<=; k++)
id[i][j][k]=++ID;
S=,T=ID+;
for (int i=; i<=N; i++)
for (int j=; j<=M; j++)
{
if (st[i][j]=='' && ed[i][j]=='')
black++,
InsertEdge(S,id[i][j][],,),
InsertEdge(id[i][j][],id[i][j][],used[i][j]/,),
InsertEdge(id[i][j][],id[i][j][],(used[i][j]+)/,);
if (st[i][j]=='' && ed[i][j]=='')
white++,
InsertEdge(id[i][j][],T,,),
InsertEdge(id[i][j][],id[i][j][],(used[i][j]+)/,),
InsertEdge(id[i][j][],id[i][j][],used[i][j]/,);
if (st[i][j]==ed[i][j])
InsertEdge(id[i][j][],id[i][j][],used[i][j]/,),
InsertEdge(id[i][j][],id[i][j][],used[i][j]/,);
}
for (int i=; i<=N; i++)
for (int j=; j<=M; j++)
for (int x,y,k=; k<; k++)
{
x=i+dx[k],y=j+dy[k];
if (check(x,y)) InsertEdge(id[i][j][],id[x][y][],INF,);
}
}
int main()
{
scanf("%d%d",&N,&M);
for (int i=; i<=N; i++) scanf("%s",st[i]+);
for (int i=; i<=N; i++) scanf("%s",ed[i]+);
for (int i=; i<=N; i++) scanf("%s",us[i]+);
for (int i=; i<=N; i++)
for (int j=; j<=M; j++) used[i][j]=us[i][j]-'';
BuildGraph();
Flow=zkw();
printf("%d\n",black==white? (Flow==black? Cost : -) : -);
return ;
}

脑残RE了好几次...

上一篇:BZOJ2668: [cqoi2012]交换棋子


下一篇:[bzoj2668] [洛谷P3159] [cqoi2012] 交换棋子