[BZOJ 3894] 文理分科 【最小割】

题目链接：BZOJ - 3894

 

题目分析

最小割模型，设定一个点与 S 相连表示选文，与 T 相连表示选理。

那么首先要加上所有可能获得的权值，然后减去最小割，即不能获得的权值。

那么对于每个点，从 S 向它连权值为它选文的价值的边，从它向 T 连权值为它选理的价值的边。

对于一个点，它和与它相邻的点构成了一个集合，这个集合如果都选文，可以获得一个价值v1，如果都选理，可以获得一个价值 v2。

只要这个集合中有一个点选文，就无法获得 v2，只要有一个点选理，就无法获得 v1。

那么处理方式就是，新开一个点，从它向 T 连 v2 的边，从这个集合中的每个点向它连 INF 边。这样，只要集合中有一个点选文，就必须割掉 v2。

v1的处理同理。

 

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int MaxN = 100 + 5, MaxNode = 30000 + 15, Dx[5] = {0, 0, 1, -1}, Dy[5] = {1, -1, 0, 0}, INF = 999999999;

int n, m, S, T, Tot, Sum, MaxFlow;
int Idx[MaxN][MaxN], Wk[MaxN][MaxN][3], Lk[MaxN][MaxN][3], Num[MaxNode], d[MaxNode];

struct Edge
{
    int v, w;
    Edge *Next, *Other;
} E[MaxNode * 16], *P = E, *Point[MaxNode], *Last[MaxNode];
 
inline void AddEdge(int x, int y, int z)
{
    Edge *Q = ++P; ++P;
    P -> v = y; P -> w = z;
    P -> Next = Point[x]; Point[x] = P; P -> Other = Q;
    Q -> v = x; Q -> w = 0;
    Q -> Next = Point[y]; Point[y] = Q; Q -> Other = P;
}
 
inline int gmin(int a, int b) {return a < b ? a : b;}
 
int DFS(int Now, int Flow)
{
    if (Now == T) return Flow;
    int ret = 0;
    for (Edge *j = Last[Now]; j; j = j -> Next)
        if (j -> w && d[Now] == d[j -> v] + 1)
        {
            Last[Now] = j;
            int p = DFS(j -> v, gmin(j -> w, Flow - ret));
            ret += p; j -> w -= p; j -> Other -> w += p;
            if (ret == Flow) return ret;
        }
    if (d[S] >= Tot) return ret;
    if (--Num[d[Now]] == 0) d[S] = Tot;
    ++Num[++d[Now]];
    Last[Now] = Point[Now];
    return ret;
}

inline bool Inside(int x, int y)
{
	if (x < 1 || x > n) return false;
	if (y < 1 || y > m) return false;
	return true;
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			Idx[i][j] = (i - 1) * m + j;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			scanf("%d", &Wk[i][j][0]);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			scanf("%d", &Lk[i][j][0]);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			scanf("%d", &Wk[i][j][1]);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			scanf("%d", &Lk[i][j][1]);
	Tot = n * m * 3; S = ++Tot; T = ++Tot;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
		{
			Sum += Wk[i][j][0] + Wk[i][j][1];
			Sum += Lk[i][j][0] + Lk[i][j][1];
			AddEdge(S, Idx[i][j], Wk[i][j][0]);
			AddEdge(Idx[i][j], T, Lk[i][j][0]);
			int x, y;
			for (int k = 0; k < 4; ++k)
			{
				x = i + Dx[k]; y = j + Dy[k];
				if (!Inside(x, y)) continue;
				AddEdge(Idx[x][y], n * m + Idx[i][j], INF);
				AddEdge(n * m * 2 + Idx[i][j], Idx[x][y], INF);	
			}
			AddEdge(Idx[i][j], n * m + Idx[i][j], INF);
			AddEdge(n * m * 2 + Idx[i][j], Idx[i][j], INF);
			AddEdge(n * m + Idx[i][j], T, Lk[i][j][1]);
			AddEdge(S, n * m * 2 + Idx[i][j], Wk[i][j][1]);
		}
	MaxFlow = 0;
	memset(d, 0, sizeof(d));
	memset(Num, 0, sizeof(Num)); Num[0] = Tot;
	for (int i = 1; i <= Tot; ++i) Last[i] = Point[i];
	while (d[S] < Tot) MaxFlow += DFS(S, INF);
	printf("%dn", Sum - MaxFlow);
	return 0;
}