2668: [cqoi2012]交換棋子

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

Description

有一個n行m列的黑白棋盤，你每次可以交換兩個相鄰格子（相鄰是指有公共邊或公共頂點）中的棋子，最終達到目標狀態。要求第i行第j列的格子只能參與m_i,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

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[50][50]; char st[50][50],ed[50][50],us[50][50]; struct EdgeNode{int next,to,cap,cost;}edge[MAXM]; int cnt=1,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,0,-c);} int dis[MAXN],S,T,Cost,Flow; bool mark[MAXN]; #define INF 0x7fffffff inline bool SPFA() {memset(mark,0,sizeof(mark));for (int i=S; i<=T; i++) dis[i]=INF;queue<int>q;q.push(S); dis[S]=0; mark[S]=1;while (!q.empty()){int now=q.front(); q.pop(); mark[now]=0;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]=1;}}return dis[T]!=INF; } inline int DFS(int loc,int low) {mark[loc]=1;if (loc==T) return low;int used=0,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^1].cap+=w; used+=w; Cost+=w*edge[i].cost;if (low==used) return used;}return used; } inline int zkw() {int re=0;while (SPFA()){mark[T]=1;while (mark[T]) memset(mark,0,sizeof(mark)),re+=DFS(S,INF);}return re; } int id[50][50][4],ID,black,white; int dx[10]={-1,-1,-1,0,0,1,1,1},dy[10]={-1,0,1,-1,1,-1,0,1}; inline bool check(int x,int y) {return x>=1 && x<=N && y>=1 && y<=M;} void BuildGraph() {for (int i=1; i<=N; i++)for (int j=1; j<=M; j++)for (int k=1; k<=3; k++)id[i][j][k]=++ID;S=0,T=ID+1;for (int i=1; i<=N; i++)for (int j=1; j<=M; j++){if (st[i][j]=='0' && ed[i][j]=='1')black++,InsertEdge(S,id[i][j][2],1,0),InsertEdge(id[i][j][1],id[i][j][2],used[i][j]/2,0),InsertEdge(id[i][j][2],id[i][j][3],(used[i][j]+1)/2,0);if (st[i][j]=='1' && ed[i][j]=='0')white++,InsertEdge(id[i][j][2],T,1,0),InsertEdge(id[i][j][1],id[i][j][2],(used[i][j]+1)/2,0),InsertEdge(id[i][j][2],id[i][j][3],used[i][j]/2,0);if (st[i][j]==ed[i][j])InsertEdge(id[i][j][1],id[i][j][2],used[i][j]/2,0),InsertEdge(id[i][j][2],id[i][j][3],used[i][j]/2,0);}for (int i=1; i<=N; i++)for (int j=1; j<=M; j++)for (int x,y,k=0; k<8; k++){x=i+dx[k],y=j+dy[k];if (check(x,y)) InsertEdge(id[i][j][3],id[x][y][1],INF,1);} } int main() {scanf("%d%d",&N,&M);for (int i=1; i<=N; i++) scanf("%s",st[i]+1);for (int i=1; i<=N; i++) scanf("%s",ed[i]+1);for (int i=1; i<=N; i++) scanf("%s",us[i]+1);for (int i=1; i<=N; i++)for (int j=1; j<=M; j++) used[i][j]=us[i][j]-'0';BuildGraph();Flow=zkw();printf("%d\n",black==white? (Flow==black? Cost : -1) : -1);return 0; }

腦殘RE了好幾次...

轉載于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5962009.html

總結

以上是生活随笔為你收集整理的【BZOJ-2668】交换棋子 最小费用最大流的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。