首页 > 代码库 > bzoj 2756
bzoj 2756
传送门http://www.lydsy.com/JudgeOnline/problem.php?id=2756
基本思路：我们考虑可以变成的最终的状态，假设每一位置的数都是x， 由于对于相连的格子一起加1， 那么我们就可以对方格进行黑白染色（相邻格子的颜色严格不同），假设个数分别为c1， c2， 总和为s1， s2， 那么 c1 * x - s1 = c2 * x - s2, x = (s1 - s2) / (c1 - c2); 当n * m % 2 == 1 时 c1 != c2, 可以反解x; 否则x在某一个值以上的时候一定都可以满足，就可以二分了。
重点就是如何检验x是否可行，然后方法是对于黑格子向原点连x - a[i][j] 的边，然后白格子向汇点连x - a[i][j]的边， 然后相邻的格子连inf的边，跑满流就可以了。
warning: 首先我们需要两个inf 分别表示流量的最大值和二分最大值，不能一样，然后二分的最小边界必须是a[i][j] 中的最大值减1，因为要保证x > Max{a[i][j]}
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long qword;const qword maxl = 50;const qword maxn = maxl * maxl;const qword dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};const qword inf = 0x3f3f3f3f;const qword infll = (1ll << 60);qword n, m, sum[2], c[2];qword a[maxl][maxl], col[maxl][maxl];struct edge { qword t, c; edge* next, *other;}e[maxn * 10]; qword ne = 0; edge* head[maxn];void addedge(qword f, qword t, qword c) { e[ne].t = t, e[ne].c = c, e[ne].next = head[f], head[f] = e + ne ++; e[ne].t = f, e[ne].c = 0, e[ne].next = head[t], head[t] = e + ne ++; e[ne - 1].other = e + ne - 2; e[ne - 2].other = e + ne - 1;}qword q[maxn], l, r; qword dis[maxn];qword s, t;bool bfs() { memset(dis, 0, sizeof(dis)); dis[s] = 1; l = r = 0; q[r ++] = s; while(l ^ r) { qword x = q[l ++]; for(edge* p = head[x]; p; p = p-> next) { if(!dis[p-> t] && p-> c) { q[r ++] = p-> t; dis[p-> t] = dis[x] + 1; } } } return (bool)dis[t];}/*qword dfs(qword x, qword flow) { if(x == t) return flow; if(!flow) return 0; qword ret = 0, maxflow; for(edge* p = head[x]; p && flow; p = p-> next) { if(p-> c && dis[p-> t] == dis[x] + 1 && (maxflow = dfs(p-> t, min(flow, p-> c)))) { p-> c -= maxflow, p-> other-> c += maxflow; ret += maxflow, flow -= maxflow; } } return ret;}*/edge* Next[maxn]; qword sta[maxn], top = 0;qword dfs() { for(qword i = s; i <= t; ++ i) Next[i] = head[i]; top = 0; sta[++ top] = s; qword ret = 0; while(top) { qword x = sta[top]; if(x == t) { qword minfl = infll + 1000; qword last; for(qword i = 1; i < top; ++ i) { if(Next[sta[i]]-> c < minfl) minfl = Next[sta[i]]-> c, last = i; } for(qword i = 1; i < top; ++ i) { edge* p = Next[sta[i]]; p-> c -= minfl, p-> other-> c += minfl; } ret += minfl, top = last; continue; } edge* px; for(px = Next[x]; px; px = px-> next) { if(dis[px-> t] == dis[x] + 1 && px-> c) { sta[++ top] = px-> t; break; } } Next[x] = px; if(Next[x] == NULL) { top --; if(Next[sta[top]]) Next[sta[top]] = Next[sta[top]]-> next; } } return ret;}qword get(qword x, qword y) { return (x - 1) * m + y;}bool flow(qword x) { ne = 0; memset(head, 0, sizeof(head)); qword tl = 0; for(qword i = 1; i <= n; ++ i) { for(qword j = 1; j <= m; ++ j) { qword tmp = x - a[i][j]; if(col[i][j] == 0) addedge(0, get(i, j), tmp); else addedge(get(i, j), t, tmp); tl += tmp; } } for(qword i = 1; i <= n; ++ i) { for(qword j = 1; j <= m; ++ j) { if(col[i][j] == 0) { for(qword l = 0; l < 4; ++ l) { qword x = i + dir[l][0]; qword y = j + dir[l][1]; if(x < 1 || x > n || y < 1 || y > m) continue; addedge(get(i, j), get(x, y), infll); } } } } qword fl = 0; while(bfs()) fl += dfs(); return (tl == fl * 2);}qword getans(qword x) { return ((n * m * x - sum[0] - sum[1]) >> 1);}void sov() { qword T; scanf("%lld", &T); qword Max = 0; while(T --) { Max = 0; scanf("%lld%lld", &n, &m); memset(sum, 0, sizeof(sum)); memset(c, 0, sizeof(c)); col[0][1] = 1; for(qword i = 1; i <= n; ++ i) { qword cl = !col[i - 1][1]; for(qword j = 1; j <= m; ++ j) { scanf("%lld", &a[i][j]); col[i][j] = cl; cl = !cl; c[col[i][j]] ++, sum[col[i][j]] += a[i][j]; Max = max(Max, a[i][j]); } } s = 0, t = n * m + 1; if(n * m % 2) { qword x = abs(sum[0] - sum[1]); if(x >= Max && flow(x)) printf("%lld\n", getans(x)); else printf("-1\n"); } else { qword ls = Max - 1, rs = inf * 1000; qword ans = -1; while(rs - ls > 1) { qword mid = (ls + rs) >> 1; if(flow(mid)) rs = mid, ans = mid; else ls = mid; } if(ans == -1) printf("-1\n"); else printf("%lld\n", getans(ans)); } }}int main() { //freopen("test.in", "r", stdin); //freopen("test.out", "w", stdout); sov(); return 0;}
bzoj 2756
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。