首页 > 代码库 > BZOJ 2756 SCOI 2012 奇怪的游戏 二分+最大流
BZOJ 2756 SCOI 2012 奇怪的游戏 二分+最大流
题目大意:给出一个棋盘,上面有一些数字,每一次可以将相邻的两个数字一起加一。问最少的次数使得整个棋盘上的数字都相等。
思路:基础思路:二分最少的相等的数字。将棋盘黑白染色,每次操作一定会使一个黑子和一个白子加1,建立二分图,S向所有白点连边,所有黑点向T连边,流量为每个点到达需要相等数字的需求大小。相邻的黑点和白点连边,f:INF。然后跑最大流看是否满流就可以了。
但是这个题需要多想一些。
因为每次会让黑点和白点同时加1,所以suma和sumb的差是不会改变的。
若m*n是偶数,那么黑点白点数量相同,若suma!=sumb则无解。
若m*n是奇数,那么可以O(1)算出可行的相等的数字,直接判断就可以出解了。
剩下的情况可以证明二分的正确性,如果可以都等于k,那么剪掉一层就变k-1了,由于m*n是偶数,所以肯定存在一种方案剪掉一层。
CODE:
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 2010 #define MAXE 210010 #define S 0 #define T (MAX - 1) #define INF (1ll << 55) using namespace std; const int dx[] = {0,1,-1,0,0}; const int dy[] = {0,0,0,1,-1}; long long all_flow; struct MaxFlow{ int head[MAX],total; int next[MAXE],aim[MAXE]; long long flow[MAXE]; int deep[MAX]; void Reset() { total = 1; memset(head,0,sizeof(head)); } void Add(int x,int y,long long f) { next[++total] = head[x]; aim[total] = y; flow[total] = f; head[x] = total; } void Insert(int x,int y,long long f) { if(x == S) all_flow += f; Add(x,y,f); Add(y,x,0); } bool BFS() { static queue<int> q; while(!q.empty()) q.pop(); memset(deep,0,sizeof(deep)); deep[S] = 1; q.push(S); while(!q.empty()) { int x = q.front(); q.pop(); for(int i = head[x]; i; i = next[i]) if(flow[i] && !deep[aim[i]]) { deep[aim[i]] = deep[x] + 1; q.push(aim[i]); if(aim[i] == T) return true; } } return false; } long long Dinic(int x,long long f) { if(x == T) return f; long long temp = f; for(int i = head[x]; i; i = next[i]) if(flow[i] && temp && deep[aim[i]] == deep[x] + 1) { long long away = Dinic(aim[i],min(flow[i],temp)); if(!away) deep[aim[i]] = 0; flow[i] -= away; flow[i^1] += away; temp -= away; } return f - temp; } }solver; int _T,m,n,cnt; int src[50][50],num[50][50]; bool color[50][50]; long long black,white,start; int b_cnt,w_cnt; inline void Initialize() { black = white = cnt = 0; b_cnt = w_cnt = 0; start = 0; memset(color,0,sizeof(color)); memset(num,0,sizeof(num)); color[1][1] = true; for(int i = 2; i <= m; ++i) color[i][1] = !color[i - 1][1]; for(int i = 1; i <= m; ++i) for(int j = 2; j <= n; ++j) color[i][j] = !color[i][j - 1]; } inline bool Judge(long long ans) { solver.Reset(); all_flow = 0; for(int i = 1; i <= m; ++i) for(int j = 1; j <= n; ++j) color[i][j] ? solver.Insert(S,num[i][j],ans - src[i][j]):solver.Insert(num[i][j],T,ans - src[i][j]); for(int i = 1; i <= m; ++i) for(int j = 1; j <= n; ++j) { if(!color[i][j]) continue; for(int k = 1; k <= 4; ++k) { int fx = i + dx[k],fy = j + dy[k]; if(!fx || !fy || fx > m || fy > n) continue; solver.Insert(num[i][j],num[fx][fy],INF); } } long long max_flow = 0; while(solver.BFS()) max_flow += solver.Dinic(S,INF); return max_flow == all_flow; } int main() { for(cin >> _T; _T--;) { scanf("%d%d",&m,&n); Initialize(); for(int i = 1; i <= m; ++i) for(int j = 1; j <= n; ++j) { scanf("%d",&src[i][j]),num[i][j] = ++cnt; start = max(start,(long long)src[i][j]); } for(int i = 1; i <= m; ++i) for(int j = 1; j <= n; ++j) { color[i][j] ? white += src[i][j]:black += src[i][j]; color[i][j] ? ++w_cnt:++b_cnt; } if(w_cnt != b_cnt) { long long mid = (black - white) / (b_cnt - w_cnt); if(mid >= start && Judge(mid)) printf("%lld\n",((long long)m * n * mid - white - black) >> 1); else puts("-1"); } else { if(black != white) { puts("-1"); continue; } long long l = start,r = INF,ans = -1; while(l <= r) { long long mid = (l + r) >> 1; if(Judge(mid)) r = mid - 1,ans = mid; else l = mid + 1; } if(ans + 1) printf("%lld\n",(ans * m * n - white - black) >> 1); else puts("-1"); } } return 0; }
BZOJ 2756 SCOI 2012 奇怪的游戏 二分+最大流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。