BZOJ 2127 happiness 最小割
题目大意:一个班级中,两个相邻的人是朋友,一对朋友如果同时选择文科或者理科会有加成。问最多能够得到的权值是多少。
思路:先假设得到所有的权值,然后运用最小割的意义求出最大的获利。具体方法见 http://hzwer.com/2422.html
CODE:
#define _CRT_SECURE_NO_WARNINGS #include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 1010 #define MAXP 5000010 #define MAXE 5000010 #define INF 0x3f3f3f3f #define S 0 #define T (MAXP - 1) using namespace std; #define P(i,j) ((i - 1) * (m) + (j)) struct MaxFlow{ int head[MAXP],total; int next[MAXE],aim[MAXE],flow[MAXE]; int deep[MAXP]; MaxFlow():total(1) {} void Add(int x,int y,int f) { next[++total] = head[x]; aim[total] = y; flow[total] = f; head[x] = total; } void Insert(int x,int y,int f) { Add(x,y,f); Add(y,x,f); } 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(!deep[aim[i]] && flow[i]) { deep[aim[i]] = deep[x] + 1; q.push(aim[i]); if(aim[i] == T) return true; } } return false; } int Dinic(int x,int f) { if(x == T) return f; int temp = f; for(int i = head[x]; i; i = next[i]) if(flow[i] && temp && deep[aim[i]] == deep[x] + 1) { int 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 m,n,ans; int s[MAX][MAX],t[MAX][MAX]; int main() { cin >> m >> n; for(int i = 1; i <= m; ++i) for(int x,j = 1; j <= n; ++j) { scanf("%d",&x); s[i][j] += x << 1; ans += (x << 1); } for(int i = 1; i <= m; ++i) for(int x,j = 1; j <= n; ++j) { scanf("%d",&x); t[i][j] += x << 1; ans += (x << 1); } for(int i = 1; i < m; ++i) for(int x,j = 1; j <= n; ++j) { scanf("%d",&x); solver.Insert(P(i,j),P(i + 1,j),x); s[i][j] += x,s[i + 1][j] += x; ans += x << 1; } for(int i = 1; i < m; ++i) for(int x,j = 1; j <= n; ++j) { scanf("%d",&x); solver.Insert(P(i,j),P(i + 1,j),x); t[i][j] += x,t[i + 1][j] += x; ans += x << 1; } for(int i = 1; i <= m; ++i) for(int x,j = 1; j < n; ++j) { scanf("%d",&x); solver.Insert(P(i,j),P(i,j + 1),x); s[i][j] += x,s[i][j + 1] += x; ans += x << 1; } for(int i = 1; i <= m; ++i) for(int x,j = 1; j < n; ++j) { scanf("%d",&x); solver.Insert(P(i,j),P(i,j + 1),x); t[i][j] += x,t[i][j + 1] += x; ans += x << 1; } for(int i = 1; i <= m; ++i) for(int j = 1; j <= n; ++j) { solver.Insert(S,P(i,j),s[i][j]); solver.Insert(P(i,j),T,t[i][j]); } int max_flow = 0; while(solver.BFS()) max_flow += solver.Dinic(S,INF); cout << (ans - max_flow) / 2 << endl; return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。