题解 【P4313 文理分科】

非常神奇的的最小割模型。

正面建立最大流/费用流模型不好搞，于是考虑最小割，发现有点东西。

建立超级源 $S$ 和超级汇 $T$，分别代表文科和理科。对于每个人 $i$，从 $S$ 到 $i$ 连一条边，边权为第 $i$ 个人选择文科获得的收益。从 $i$ 到 $T$ 连一条边，边权为第 $i$ 个人选择理科获得的收益。

以上完全是凭直觉建出来的模型，考虑一下它是否正确。显然如果第 $i$ 个人既选了文科又选了理科，一定存在 $S\rightarrow i\rightarrow T$ 这条路径从 $S$ 到达 $T$。因此该模型正确。

现在加入相邻的人同时选择文/理科的收益。直接在这些点之间连边非常不好搞，所以对于每个人新建一个点 ，假设这个人为 $i$，新建的点为 $i^{\prime}$。那么从 $i^{\prime}$ 向 $i$ 以及所有与第 $i$ 个人相邻的人连一条边权为 $\infty$ 的边，因为显然这些边不可以割掉。然后从 $S$ 向 $i^{\prime}$ 连一条边，边权为 $i$ 与它相邻的人同时选文科的收益。同理，从 $i^{\prime}$ 向 $S$ 连一条边，边权为 $i$ 与它相邻的人同时选理科的收益

再次考虑新模型的正确性。假设我获得了 $S\rightarrow i^{\prime}$ 这条边的收益，即与 $i$ 相邻的人全选了文科。那么只要有一个与 $i$ 相邻的人 $j$ 背叛组织，选择了理科，那么就存在一条 $S\rightarrow i^{\prime}\rightarrow j\rightarrow T$ 的路径可以从 $S$ 到达 $T$。因为根据假设，$S\rightarrow i^{\prime}$ 以及 $j\rightarrow T$ 这两条边存在，而 $i^{\prime}\rightarrow j$ 这条边又是不可以割掉的（边权为INF），所以模型正确。

把边权换成流量跑 ISAP 就行了。当然你要 Dinic 也可以虽然跑得慢

#include <cstdio>
#include <queue>
#include <cstring>

const int INF = 1e9;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
	int to, nxt, cap;
} e[1000005];
int head[100005], cur[100005], dep[100005], num[100005], s, t, tot = 1, cnt;
int ar[105][105], sc[105][105];
std::queue<int> Q;
inline void AddEdge(const int u, const int v, const int cap) {
	e[++ tot].to = v, e[tot].cap = cap, e[tot].nxt = head[u], head[u] = tot;
	e[++ tot].to = u, e[tot].cap = 0, e[tot].nxt = head[v], head[v] = tot;
}

void bfs() {
	memcpy(cur, head, sizeof cur);
	num[dep[t] = 1] = 1;
	Q.push(t);
	while (Q.size()) {
		int u(Q.front());
		Q.pop();
		for (int i(head[u]); i; i = e[i].nxt)
			if (!dep[e[i].to]) ++ num[dep[e[i].to] = dep[u] + 1], Q.push(e[i].to);
	}
}

int dfs(const int u, const int flow) {
	if (u == t) return flow;
	int used(0), tmp(0);
	for (int i(cur[u]); i; i = e[i].nxt) {
		cur[u] = i;
		if (e[i].cap && dep[u] - 1 == dep[e[i].to]) {
			tmp = dfs(e[i].to, min(e[i].cap, flow - used));
			e[i].cap -= tmp, e[i ^ 1].cap += tmp, used += tmp;
			if (used == flow) return used;
		}
	}
	cur[u] = head[u];
	if (!(-- num[dep[u]])) dep[s] = cnt + 2;
	++ num[++ dep[u]];
	return used;
}

int ISAP() {
	int Maxflow(0);
	bfs();
	while (dep[s] <= cnt + 1) Maxflow += dfs(s, INF);
	return Maxflow;
}

int main()  {
	int n, m, ans(0);
	scanf("%d%d", &n, &m);
	s = 0, t = (cnt = n * m + 1);
	for (int i(1); i <= n; ++ i)
	for (int j(1); j <= m; ++ j) {
		int x;
		scanf("%d", &x);
		AddEdge(s, (i - 1) * m + j, x), ans += x;
	}
	for (int i(1); i <= n; ++ i)
	for (int j(1); j <= m; ++ j) {
		int x;
		scanf("%d", &x);
		AddEdge((i - 1) * m + j, t, x), ans += x;
	}
	for (int i(1); i <= n; ++ i)
	for (int j(1); j <= m; ++ j) {
		int x, u(++ cnt);
		scanf("%d", &x);
		AddEdge(s, u, x), ans += x;
		AddEdge(u, (i - 1) * m + j, INF);
		for (int k(0); k <= 3; ++ k) {
			int tx(i + dx[k]), ty(j + dy[k]);
			if (tx < 1 || ty < 1 || n < tx || m < ty) continue;
			AddEdge(u, (tx - 1) * m + ty, INF);
		}
	}
	for (int i(1); i <= n; ++ i)
	for (int j(1); j <= m; ++ j) {
		int x, u(++ cnt);
		scanf("%d", &x);
		AddEdge(u, t, x), ans += x;
		AddEdge((i - 1) * m + j, u, INF);
		for (int k(0); k <= 3; ++ k) {
			int tx(i + dx[k]), ty(j + dy[k]);
			if (tx < 1 || ty < 1 || n < tx || m < ty) continue;
			AddEdge((tx - 1) * m + ty, u, INF);
		}
	}
	printf("%d", ans - ISAP());
}