2668: [cqoi2012]交換棋子

Time Limit:?3 Sec??Memory Limit:?128 MB
Submit:?1112??Solved:?409
[Submit][Status][Discuss]

Description

有一個(gè)n行m列的黑白棋盤，你每次可以交換兩個(gè)相鄰格子（相鄰是指有公共邊或公共頂點(diǎn)）中的棋子，最終達(dá)到目標(biāo)狀態(tài)。要求第i行第j列的格子只能參與m_i,j次交換。

Input

第一行包含兩個(gè)整數(shù)n，m（1<=n,?m<=20）。以下n行為初始狀態(tài)，每行為一個(gè)包含m個(gè)字符的01串，其中0表示黑色棋子，1表示白色棋子。以下n行為目標(biāo)狀態(tài)，格式同初始狀態(tài)。以下n行每行為一個(gè)包含m個(gè)0~9數(shù)字的字符串，表示每個(gè)格子參與交換的次數(shù)上限。

Output

輸出僅一行，為最小交換總次數(shù)。如果無(wú)解，輸出-1。

Sample Input

3 3
110
000
001
000
110
100
222
222
222

Sample Output

4

HINT

Source

[Submit][Status][Discuss]

?

對(duì)于每一個(gè)格子,拆成三個(gè)點(diǎn),分別為x,y,z。

其中，x為格子間轉(zhuǎn)移邊的入點(diǎn)，z為出點(diǎn)，y為與S和T的連接點(diǎn)。

S向每個(gè)原圖中黑色，新圖中白色的y點(diǎn)連一條容量為1，費(fèi)用為0的邊，流過(guò)這條邊表示把該棋子換走替代其他棋子。

T向每個(gè)原圖中白色，新圖中黑色的y點(diǎn)連一條容量為1，費(fèi)用為0的邊，流經(jīng)這條邊表示用其他棋子把該棋子換走。

所有原圖中黑色，新圖中白色的點(diǎn)，x向y連容量為$\frac{limit_{i,j}}{2}$，費(fèi)用為0的邊，表示至多接受這么多替換；y向z連容量為$\frac{limit_{i,j}+1}{2}$，費(fèi)用為0的邊，表示之多提供這么多替換。所有原圖中黑色，新圖中白色的點(diǎn)，和這個(gè)反著連。新圖原圖中一樣的，容量則都是$\frac{limit_{i,j}}{2}$。

按照八聯(lián)通，所有相鄰點(diǎn)對(duì)，連接其對(duì)應(yīng)為x,z即可，容量無(wú)限，費(fèi)用為1，表示交換一次的代價(jià)為1。

?

1 #include <bits/stdc++.h> 2 #define rep(a,b,c) for(register int a=b;a<=c;++a) 3 const int mxn = 25, siz = 500005, inf = 1e9, mv[4][2] = {{0,1},{1,0},{1,1},{1,-1}}; 4 char a[mxn][mxn], b[mxn][mxn], c[mxn][mxn]; 5 int n, m, d[mxn][mxn], id[mxn][mxn][3], ID, cnt0, cnt1; 6 int s, t, tot, hd[siz], to[siz], nt[siz], fl[siz], vl[siz], dis[siz], pre[siz], que[siz], inq[siz], cost; 7 inline bool legal(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= m; } 8 inline void add(int u, int v, int f, int w) { 9 nt[tot] = hd[u]; to[tot] = v; fl[tot] = f; vl[tot] = +w; hd[u] = tot++; 10 nt[tot] = hd[v]; to[tot] = u; fl[tot] = 0; vl[tot] = -w; hd[v] = tot++; 11 } 12 inline bool spfa(void) { 13 register int head = 0, tail = 0; 14 rep(i, s, t)dis[i] = inf, inq[i] = 0; 15 dis[que[tail++] = s] = 0, inq[s] = 1, pre[s] = -1; 16 while (head != tail) { 17 int u = que[head++], v, i; inq[u] = 0; 18 for (i = hd[u]; ~i; i = nt[i])if (fl[i] && dis[v = to[i]] > dis[u] + vl[i]) { 19 dis[v] = dis[u] + vl[i], pre[v] = i^1; if (!inq[v])inq[que[tail++] = v] = 1; 20 } 21 } 22 return dis[t] < inf; 23 } 24 inline int maxFlow(void) { 25 int ret = 0; 26 while (spfa()) { 27 int flow = inf, i; 28 for (i = pre[t]; ~i; i = pre[to[i]])if (flow > fl[i^1])flow = fl[i^1]; 29 for (i = pre[t]; ~i; i = pre[to[i]])fl[i] += flow, fl[i^1] -= flow; 30 ret += flow, cost += flow * dis[t]; 31 } 32 return ret; 33 } 34 signed main(void) { 35 scanf("%d%d", &n, &m); 36 s = 0, t = n * m * 3 + 1; 37 memset(hd, -1, sizeof(hd)); 38 rep(i, 1, n)scanf("%s", a[i] + 1); 39 rep(i, 1, n)scanf("%s", b[i] + 1); 40 rep(i, 1, n)scanf("%s", c[i] + 1); 41 rep(i, 1, n)rep(j, 1, m)d[i][j] = c[i][j] - '0'; 42 rep(i, 1, n)rep(j, 1, m)rep(k, 0, 2)id[i][j][k] = ++ID; 43 rep(i, 1, n)rep(j, 1, m) { 44 if (a[i][j] == '0' && b[i][j] == '1') 45 add(s, id[i][j][1], 1, 0), ++cnt0, 46 add(id[i][j][0], id[i][j][1], d[i][j] >> 1, 0), 47 add(id[i][j][1], id[i][j][2], (d[i][j] + 1) >> 1, 0); 48 if (a[i][j] == '1' && b[i][j] == '0') 49 add(id[i][j][1], t, 1, 0), ++cnt1, 50 add(id[i][j][0], id[i][j][1], (d[i][j] + 1) >> 1, 0), 51 add(id[i][j][1], id[i][j][2], d[i][j] >> 1, 0); 52 if (a[i][j] == b[i][j]) 53 add(id[i][j][0], id[i][j][1], d[i][j] >> 1, 0), 54 add(id[i][j][1], id[i][j][2], d[i][j] >> 1, 0); 55 } 56 rep(i, 1, n)rep(j, 1, m)rep(k, 0, 3)if (legal(i + mv[k][0], j + mv[k][1])) 57 add(id[i][j][2], id[i + mv[k][0]][j + mv[k][1]][0], inf, 1), 58 add(id[i + mv[k][0]][j + mv[k][1]][2], id[i][j][0], inf, 1); 59 printf("%d\n", cnt0 == cnt1 && cnt0 == maxFlow() ? cost : -1); 60 }

?

@Author: YouSiki

轉(zhuǎn)載于:https://www.cnblogs.com/yousiki/p/6269410.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 2668: [cqoi2012]交换棋子的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。