2668: [cqoi2012]交换棋子

Time Limit: 3 Sec  Memory Limit: 128 MB

Submit: 1112  Solved: 409

[][][]

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

 

[ ][ ][ ]

 

对于每一个格子,拆成三个点,分别为x,y,z。

其中，x为格子间转移边的入点，z为出点，y为与S和T的连接点。

S向每个原图中黑色，新图中白色的y点连一条容量为1，费用为0的边，流过这条边表示把该棋子换走替代其他棋子。

T向每个原图中白色，新图中黑色的y点连一条容量为1，费用为0的边，流经这条边表示用其他棋子把该棋子换走。

所有原图中黑色，新图中白色的点，x向y连容量为$\frac{limit_{i,j}}{2}$，费用为0的边，表示至多接受这么多替换；y向z连容量为$\frac{limit_{i,j}+1}{2}$，费用为0的边，表示之多提供这么多替换。所有原图中黑色，新图中白色的点，和这个反着连。新图原图中一样的，容量则都是$\frac{limit_{i,j}}{2}$。

按照八联通，所有相邻点对，连接其对应为x,z即可，容量无限，费用为1，表示交换一次的代价为1。

 

1 #include 
     
       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