@bzoj - 2668@ [cqoi2012]交换棋子

Love The Way You Lie 2023-06-01 14:56 140阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

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

## @solution@ ##

首先假如黑色棋子通过交换移动到了目标状态，那么白色棋子也就相应地变为了目标状态。  
这意味着我们可以将黑色棋子视为 “有棋子”，白色棋子视为 “空格子”，将交换视为 “移动某个棋子到一个相邻的空格子”（因为不可能同色棋子之间交换）。

假如一个格子 p 起始情况是有棋子，终止情况也是有棋子，那么我们可以视作这个地方没有棋子。  
为什么呢？假如 p 的棋子移动到了 x，而另一个 y 的棋子移动到了 p。它等价于没有 p 的棋子，y 直接移动到 x。  
上面的思路其实还告诉我们，棋子与棋子之间是不会互相阻挡的（如果阻挡了就可以像上面一样等效替换掉）。

于是，起始情况有棋子而终止情况没有棋子的 p 需要移动到 终末情况有棋子而起始情况没有棋子的 q。  
这非常像二分图匹配问题，可以使我们联想到网络流。

但是网络流建模中，没有很好的办法限制 “交换次数”。  
假如一个格子起始情况与终末情况相同，那么其他棋子进这个格子的次数 = 出这个格子的次数。这个是比较显然的。  
所以我们最多会有 \\(\\lfloor \\frac\{m\_\{i, j\}\}\{2\}\\rfloor\\) 个棋子经过这个格子，这样就可以把格子拆点，把边容量设为 \\(\\lfloor \\frac\{m\_\{i, j\}\}\{2\}\\rfloor\\)。  
不同的情况，可以类似于上面推导出最多会有 \\(\\lceil \\frac\{m\_\{i, j\}\}\{2\}\\rceil\\)（包括一开始的棋子移出去和最后的棋子移进来） 个棋子经过这个格子。

于是建图就比较明显了：  
对于初始状态与目标状态相同的 (i, j)，拆点 x -> x'，中间连容量为 \\(\\lfloor \\frac\{m\_\{i, j\}\}\{2\}\\rfloor\\) 的边。  
对于初始状态有棋子，目标状态无棋子的 (i, j)，拆点 x -> x'，中间连容量为 \\(\\lceil \\frac\{m\_\{i, j\}\}\{2\}\\rceil\\) 的边；源点 s 向 x 连容量为 1 的边。  
对于初始状态无棋子，目标状态有棋子的 (i, j)，拆点 x -> x'，中间连容量为 \\(\\lceil \\frac\{m\_\{i, j\}\}\{2\}\\rceil\\) 的边；x' 向汇点 t 连容量为 1 的边。  
对于相邻的两个格子，之间连容量为 inf 的双向边。

跑最大流看是否满流。

## @accepted code@ ##

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN = 20; const int INF = (1<<30); const int MAXV = 2*MAXN*MAXN; const int MAXE = 45*MAXV + 5; const int dx[] = {0, 1, -1}; const int dy[] = {1, -1, 0}; struct FlowGraph{ struct edge{ int to, cap, flow, cost; edge *nxt, *rev; }edges[MAXE + 5], *adj[MAXV + 5], *cur[MAXV + 5], *ecnt; FlowGraph() {ecnt = &edges[0];} int s, t, cost; void addedge(int u, int v, int c, int w) { edge *p = (++ecnt), *q = (++ecnt); p->to = v, p->cap = c, p->flow = 0, p->cost = w; p->nxt = adj[u], adj[u] = p; q->to = u, q->cap = 0, q->flow = 0, q->cost = -w; q->nxt = adj[v], adj[v] = q; p->rev = q, q->rev = p; } int f[MAXV + 5], hp[MAXV + 5]; void update(int x, int k) { f[x] = k; while( x ) { hp[x] = x; if( (x<<1) <= t && f[hp[x]] > f[hp[x<<1]] ) hp[x] = hp[x<<1]; if( (x<<1|1) <= t && f[hp[x]] > f[hp[x<<1|1]]) hp[x] = hp[x<<1|1]; x >>= 1; } } int d[MAXV + 5], h[MAXV + 5]; bool relabel() { for(int i=1;i<=t;i++) h[i] += d[i], d[i] = f[i] = INF, hp[i] = i, cur[i] = adj[i]; d[s] = 0; update(s, 0); while( f[hp[1]] != INF ) { int x = hp[1]; update(x, INF); for(edge *p=adj[x];p;p=p->nxt) { int w = p->cost + h[x] - h[p->to]; if( d[x] + w < d[p->to] && p->cap > p->flow ) { d[p->to] = d[x] + w; update(p->to, d[p->to]); } } } return !(d[t] == INF); } bool vis[MAXV + 5]; int aug(int x, int tot) { if( x == t ) return tot; int sum = 0; vis[x] = true; for(edge *&p=cur[x];p;p=p->nxt) { int w = p->cost + h[x] - h[p->to]; if( d[x] + w == d[p->to] && p->cap > p->flow && !vis[p->to] ) { int del = aug(p->to, min(tot - sum, p->cap - p->flow)); p->flow += del, p->rev->flow -= del, sum += del; if( sum == tot ) break; } } vis[x] = false; return sum; } int min_cost_max_flow(int _s, int _t) { s = _s, t = _t, cost = 0; int flow = 0; while( relabel() ) { int del = aug(s, INF); flow += del, cost += del*(d[t] + h[t]); } return flow; } }G; int n, m; int A[MAXN + 5][MAXN + 5], B[MAXN + 5][MAXN + 5]; int C[MAXN + 5][MAXN + 5], id[MAXN + 5][MAXN + 5]; char str[MAXN + 5]; int main() { scanf("%d%d", &n, &m); for(int i=1;i<=n;i++) { scanf("%s", str + 1); for(int j=1;j<=m;j++) A[i][j] = str[j] - '0'; } for(int i=1;i<=n;i++) { scanf("%s", str + 1); for(int j=1;j<=m;j++) B[i][j] = str[j] - '0'; } for(int i=1;i<=n;i++) { scanf("%s", str + 1); for(int j=1;j<=m;j++) C[i][j] = str[j] - '0'; } int cnt = 0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) id[i][j] = (++cnt); int s = 2*cnt + 1, t = 2*cnt + 2, tot1 = 0, tot2 = 0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if( A[i][j] == B[i][j] ) G.addedge(id[i][j], id[i][j] + cnt, C[i][j] / 2, 0); else if( A[i][j] == 1 && B[i][j] == 0 ) { G.addedge(s, id[i][j], 1, 0); tot1++; G.addedge(id[i][j], id[i][j] + cnt, (C[i][j] + 1) / 2, 0); } else if( A[i][j] == 0 && B[i][j] == 1 ) { G.addedge(id[i][j] + cnt, t, 1, 0); tot2++; G.addedge(id[i][j], id[i][j] + cnt, (C[i][j] + 1) / 2, 0); } for(int k=0;k<3;k++) for(int l=0;l<3;l++) { if( dx[k] == 0 && dy[l] == 0 ) continue; int x = i + dx[k], y = j + dy[l]; if( 1 <= x && x <= n && 1 <= y && y <= m ) G.addedge(id[i][j] + cnt, id[x][y], INF, 1); } } if( tot1 == tot2 && G.min_cost_max_flow(s, t) == tot1 ) printf("%d\n", G.cost); else puts("-1"); }

## @details@ ##

两个比较坑的点。  
第一个是，它向周围的八连通连边，而不是通常我们常做的四连通。  
第二个是，它起始状态与目标状态的棋子数量不一定保证相同。  
其实本质上都是读题读仔细了都能解决的问题

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11416040.html