BZOJ 3894: 文理分科

Description

 文理分科是一件很纠结的事情!(虽然看到这个题目的人肯定都没有纠结过)
 小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行描述,每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式
得到:
1.如果第i行第秒J的同学选择了文科,则他将获得art[i][j]的满意值,如果选择理科,将得到science[i][j]的满意值。
2.如果第i行第J列的同学选择了文科,并且他相邻(两个格子相邻当且仅当它们拥有一条相同的边)的同学全部选择了文科,则他会更开心,所以会增加same_art[i][j]的满意值。
3.如果第i行第j列的同学选择了理科,并且他相邻的同学全部选择了理科,则增加same_science[i]j[]的满意值。
  小P想知道,大家应该如何选择,才能使所有人的满意值之和最大。请告诉他这个最大值。

Input

第一行为两个正整数:n,m
接下来n术m个整数,表示art[i][j];
接下来n术m个整数.表示science[i][j];
接下来n术m个整数,表示same_art[i][j];

Output

输出为一个整数,表示最大的满意值之和

Sample Input

3 4
13 2 4 13
7 13 8 12
18 17 0 5
8 13 15 4
11 3 8 11
11 18 6 51 2 3 4
4 2 3 2
3 1 0 43 2 3 2
0 2 2 1
0 2 4 4

Sample Output

152

HINT

样例说明
1表示选择文科,0表示选择理科,方案如下:
1  0  0  1
0  1  0  0
1  0  0  0
N,M<=100,读入数据均<=500

Solution

又是一道神奇的最小割!
请看神犇题解:PoPoQQQ’s Bloghttp://blog.csdn.net/PoPoQQQ/article/details/43968017
神犇已经说得很详细了,我也不班门弄斧,来表示一下自己体会吧。
最小割建模好神奇的,这道题每割掉一条边,表示某人不学理科/文科。
处理相邻十字的时候,我们可以新建一个点,把五个点连接到这个点上,流量INF,因此最小割一定割不掉这个边。

Code

#include <iostream>
#include <cstdio>
using namespace std;
const int INF = 1<<30;
typedef long long LL;
int getint() {
	int r = 0, k = 1; char c = getchar();
	for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
	for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
	return r * k;
}
int n, m, S, T, id[105][105], wen[105][105], li[105][105];
const int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};

const int maxedge = 1000005;
const int maxnode = 50005;
struct MaxFlowSolver {
	int S, T;
	struct edge_type {
		int to, next, r;
	} edge[maxedge];
	int h[maxnode], cur[maxnode], dis[maxnode], cnte, L, R;
	void init() {
		cnte = 1;
		for (int i = 0; i < maxnode; ++i) h[i] = 0;
		S = T = 0;
		L = maxnode;
		R = 0;
	}
	void range(int l, int r) { L = l; R = r; }
	void ins(int u, int v, int w) {
		edge[++cnte].to = v;
		edge[cnte].next = h[u];
		edge[cnte].r = w;
		h[u] = cnte;
		edge[++cnte].to = u;
		edge[cnte].next = h[v];
		edge[cnte].r = 0;
		h[v] = cnte;
	}
	int q[maxnode];
	bool BFS() {
		int head = 0, tail = 1;
		q[0] = S;
		for (int i = L; i <= R; ++i) dis[i] = -1;
		dis[S] = 0;
		int now;
		while (head < tail) {
			now = q[head++];
			for (int i = h[now]; i; i = edge[i].next) {
				if (dis[edge[i].to] == -1 && edge[i].r) {
					dis[edge[i].to] = dis[now] + 1;
					q[tail++] = edge[i].to;
				}
			}
		}
		return dis[T] != -1;
	}
	int DFS(int now, int a) {
		if (now == T || a == 0) return a;
		int f, ret = 0;
		for (int &i = cur[now]; i; i = edge[i].next) {
			if (dis[edge[i].to] != dis[now] + 1) continue;
			if (f = DFS(edge[i].to, min(a, edge[i].r))) {
				a -= f;
				ret += f;
				edge[i].r -= f;
				edge[i^1].r += f;
				if (!a) break;
			}
		}
		if (!ret) dis[now] = -1;
		return ret;
	}
	int Dinic(int start, int end) {
		S = start; T = end;
		int ret = 0;
		while (BFS()) {
			for (int i = L; i <= R; ++i) cur[i] = h[i];
			ret += DFS(S, INF);
		}
		return ret;
	}
} G;

int main() {
	G.init();
	n = getint(); m = getint();
	int sum = 0;
	S = 1; T = 2;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			id[i][j] = T++;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			wen[i][j] = T++;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			li[i][j] = T++;
	int x;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			x = getint();
			sum += x;
			G.ins(S, id[i][j], x);
		}
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			x = getint();
			sum += x;
			G.ins(id[i][j], T, x);
		}
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			x = getint();
			sum += x;
			G.ins(S, wen[i][j], x);
			G.ins(wen[i][j], id[i][j], INF);
			for (int k = 0; k < 4; ++k) {
				int tx = i + dx[k], ty = j + dy[k];
				if (1<=tx&&tx<=n&&1<=ty&&ty<=m)
					G.ins(wen[i][j], id[tx][ty], INF);
			}
		}
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			x = getint();
			sum += x;
			G.ins(li[i][j], T, x);
			G.ins(id[i][j], li[i][j], INF);
			for (int k = 0; k < 4; ++k) {
				int tx = i + dx[k], ty = j + dy[k];
				if (1<=tx&&tx<=n&&1<=ty&&ty<=m)
					G.ins(id[tx][ty], li[i][j], INF);
			}
		}
	G.range(S, T);
	int ans = G.Dinic(S, T);
	printf("%d", sum - ans);
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据