BZOJ 2127 happiness最小カット
一つのクラスの中で、隣の二人は友達です.一つの友達は同時に文系か理科を選ぶと、プラスになります.一番多く入手できる権利はいくらですか?
考え:まず、すべての権利を得て、最小の意味で最大の利益を求めると仮定します.具体的な方法について http://hzwer.com/2422.html
コード:
考え:まず、すべての権利を得て、最小の意味で最大の利益を求めると仮定します.具体的な方法について http://hzwer.com/2422.html
コード:
#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;
}