2756: [SCOI2012]奇怪的游戏
Time Limit: 40 Sec Memory Limit: 128 MBSubmit: 3410 Solved: 941
[Submit][Status][Discuss]
Description
Blinker最近喜欢上一个奇怪的游戏。
这个游戏在一个 N*M 的棋盘上玩，每个格子有一个数。每次 Blinker 会选择两个相邻
的格子，并使这两个数都加上 1。
现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同
一个数则输出-1。
Input
输入的第一行是一个整数T，表示输入数据有T轮游戏组成。
每轮游戏的第一行有两个整数N和M， 分别代表棋盘的行数和列数。
接下来有N行，每行 M个数。
Output
对于每个游戏输出最少能使游戏结束的次数，如果永远不能变成同一个数则输出-1。
Sample Input
2
2 2
1 2
2 3
3 3
1 2 3
2 3 4
4 3 2
2 2
1 2
2 3
3 3
1 2 3
2 3 4
4 3 2
Sample Output
2
-1
-1
HINT
【数据范围】
对于30%的数据，保证 T<=10，1<=N,M<=8
对于100%的数据，保证 T<=10，1<=N,M<=40，所有数为正整数且小于1000000000
Source
二分答案 + 网络流判断
不难看出，对棋盘进行黑白染色之后，每次相加都会使得相邻的一黑一白两个格子同时+1,。
先对所有黑白格子进行统计，处理出$cnt0$,$cnt1$分别代表黑、白格子个数，处理出$sum0$,$sum1$分别代表黑、白格子权值和。
分类讨论如下：
如果$cnt0=cnt1$
如果$sum0 ot =sum1$，那么一定不存在合法解
如果$sum0=sum1$，设最终所有数字都变成$ans$，发现如果$ans$满足，则$ans+1$必定也满足，即$ans$满足二分性质，因此可以二分答案，网络流判断是否可行。
如果$cnt0 ot =cnt1$
依旧设最终数字为$ans$，则有$cnt0 imes ans-sum0=cnt1 imes ans-sum1$，化简得$ans=frac{sum0-sum1}{cnt0-cnt1}$，只需要检查这个值是否合法即可。
网络流判断可行的方法：
从S向每个黑点连$ans-Val_{i,j}$的边，从每个白点向T连$ans-Val_{i,j}$的边，相邻的黑点向白点连$+infty$的边，判断是否满流。
1 #include <bits/stdc++.h> 2 3 inline char nextChar(void) 4 { 5 static const int siz = 1 << 20; 6 7 static char buf[siz]; 8 static char *hd = buf + siz; 9 static char *tl = buf + siz; 10 11 if (hd == tl) 12 fread(hd = buf, 1, siz, stdin); 13 14 return *hd++; 15 } 16 17 inline int nextInt(void) 18 { 19 register int ret = 0; 20 register bool neg = false; 21 register char bit = nextChar(); 22 23 for (; bit < 48; bit = nextChar()) 24 if (bit == '-')neg ^= true; 25 26 for (; bit > 47; bit = nextChar()) 27 ret = ret * 10 + bit - '0'; 28 29 return neg ? -ret : ret; 30 } 31 32 typedef long long lnt; 33 34 const int siz = 50; 35 const int pnt = 2000; 36 const int edg = 2000005; 37 const lnt inf = 2e18 + 9; 38 39 int tot; 40 int S, T; 41 int hd[pnt]; 42 int nt[edg]; 43 int to[edg]; 44 lnt fl[edg]; 45 46 inline void addEdge(int u, int v, lnt f) 47 { 48 nt[tot] = hd[u]; to[tot] = v; fl[tot] = f; hd[u] = tot++; 49 nt[tot] = hd[v]; to[tot] = u; fl[tot] = 0; hd[v] = tot++; 50 } 51 52 int dep[pnt]; 53 54 inline bool bfs(void) 55 { 56 static int que[pnt]; 57 static int head, tail; 58 59 memset(dep, 0, sizeof(dep)); 60 que[head = 0] = S, tail = dep[S] = 1; 61 62 while (head != tail) 63 { 64 int u = que[head++], v; 65 66 for (int i = hd[u]; ~i; i = nt[i]) 67 if (fl[i] && !dep[v = to[i]]) 68 dep[que[tail++] = v] = dep[u] + 1; 69 } 70 71 return dep[T]; 72 } 73 74 int cur[pnt]; 75 76 inline lnt min(lnt a, lnt b) 77 { 78 return a < b ? a : b; 79 } 80 81 lnt dfs(int u, lnt f) 82 { 83 if (!f || u == T) 84 return f; 85 86 lnt used = 0, flow; 87 88 for (int i = cur[u], v; ~i; i = nt[i]) 89 if (fl[i] && dep[v = to[i]] == dep[u] + 1) 90 { 91 flow = dfs(v, min(fl[i], f - used)); 92 93 used += flow; 94 fl[i] -= flow; 95 fl[i^1] += flow; 96 97 if (fl[i]) 98 cur[u] = i; 99 100 if (used == f) 101 return f; 102 } 103 104 if (!used) 105 dep[u] = 0; 106 107 return used; 108 } 109 110 inline lnt maxFlow(void) 111 { 112 lnt maxFlow = 0, newFlow; 113 114 while (bfs()) 115 { 116 memcpy(cur, hd, sizeof(hd)); 117 118 while (newFlow = dfs(S, inf)) 119 maxFlow += newFlow; 120 } 121 122 return maxFlow; 123 } 124 125 int n, m; 126 lnt num[siz][siz]; 127 128 const int mv[4][2] = 129 { 130 {0, 1}, 131 {1, 0}, 132 {0, -1}, 133 {-1, 0} 134 }; 135 136 inline bool legal(int x, int y) 137 { 138 if (x < 1 || x > n)return false; 139 if (y < 1 || y > m)return false; 140 141 return true; 142 } 143 144 inline int pos(int x, int y) 145 { 146 return (x - 1) * m + y; 147 } 148 149 inline bool check(lnt ans) 150 { 151 lnt sum = 0; 152 153 S = 0, T = n * m + 1; 154 155 memset(hd, -1, sizeof(hd)), tot = 0; 156 157 for (int i = 1; i <= n; ++i) 158 for (int j = 1; j <= m; ++j) 159 { 160 if ((i ^ j) & 1) 161 { 162 sum += ans - num[i][j]; 163 164 addEdge(S, pos(i, j), ans - num[i][j]); 165 166 for (int k = 0; k < 4; ++k) 167 { 168 int x = i + mv[k][0]; 169 int y = j + mv[k][1]; 170 171 if (legal(x, y)) 172 addEdge(pos(i, j), pos(x, y), inf); 173 } 174 } 175 else 176 addEdge(pos(i, j), T, ans - num[i][j]); 177 } 178 179 return sum == maxFlow(); 180 } 181 182 inline lnt calc(lnt ans) 183 { 184 lnt ret = 0; 185 186 for (int i = 1; i <= n; ++i) 187 for (int j = 1; j <= m; ++j) 188 ret += ans - num[i][j]; 189 190 return ret >> 1; 191 } 192 193 inline lnt maxNum(void) 194 { 195 lnt ret = 0; 196 197 for (int i = 1; i <= n; ++i) 198 for (int j = 1; j <= m; ++j) 199 if (ret < num[i][j]) 200 ret = num[i][j]; 201 202 return ret; 203 } 204 205 signed main(void) 206 { 207 for (int cas = nextInt(); cas--; ) 208 { 209 n = nextInt(); 210 m = nextInt(); 211 212 for (int i = 1; i <= n; ++i) 213 for (int j = 1; j <= m; ++j) 214 num[i][j] = nextInt(); 215 216 int cnt0 = 0, cnt1 = 0; 217 lnt sum0 = 0, sum1 = 0; 218 219 for (int i = 1; i <= n; ++i) 220 for (int j = 1; j <= m; ++j) 221 if ((i ^ j) & 1) 222 ++cnt1, sum1 += num[i][j]; 223 else 224 ++cnt0, sum0 += num[i][j]; 225 226 if (cnt0 == cnt1) 227 { 228 if (sum0 != sum1) 229 puts("-1"); 230 else 231 { 232 lnt lt = maxNum(), rt = 1LL << 50, mid, ans = -1; 233 234 while (lt <= rt) 235 { 236 mid = (lt + rt) >> 1; 237 238 if (check(mid)) 239 rt = mid - 1, ans = mid; 240 else 241 lt = mid + 1; 242 } 243 244 if (~ans) 245 printf("%lld ", calc(ans)); 246 else 247 puts("-1"); 248 } 249 } 250 else 251 { 252 lnt ans = (sum0 - sum1) / (cnt0 - cnt1); 253 254 if (ans < maxNum() || !check(ans)) 255 puts("-1"); 256 else 257 printf("%lld ", calc(ans)); 258 } 259 } 260 }
@Author: YouSiki