[BZOJ 2127] happiness 【最小割】

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

using namespace std;

const int MaxN = 100 + 5, MaxNode = 10000 + 15, INF = 999999999;

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

struct Edge
{
	int v, w;
	Edge *Next, *Other;
} E[MaxNode * 12], *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;
}

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;
	S = n * m + 1; T = n * m + 2; Tot = T;
	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 - 1; ++i)
		for (int j = 1; j <= m; ++j)
			scanf("%d", &Wk[i][j][1]);
	for (int i = 1; i <= n - 1; ++i)
		for (int j = 1; j <= m; ++j)
			scanf("%d", &Lk[i][j][1]);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m - 1; ++j)
			scanf("%d", &Wk[i][j][2]);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m - 1; ++j)
			scanf("%d", &Lk[i][j][2]);
	int v1, v2, v3;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
		{
			Sum += Wk[i][j][0] + Wk[i][j][1] + Wk[i][j][2];
			Sum += Lk[i][j][0] + Lk[i][j][1] + Lk[i][j][2];
			v1 = Wk[i][j][0] * 2 + Wk[i][j][1] + Wk[i][j][2]; 
			v2 = Lk[i][j][0] * 2 + Lk[i][j][1] + Lk[i][j][2];
			v1 += Wk[i - 1][j][1]; v2 += Lk[i - 1][j][1];
			v1 += Wk[i][j - 1][2]; v2 += Lk[i][j - 1][2];
			AddEdge(S, Idx[i][j], v1);
			AddEdge(Idx[i][j], T, v2);
			if (i < n)
			{
				v3 = Wk[i][j][1] + Lk[i][j][1];
				AddEdge(Idx[i][j], Idx[i + 1][j], v3);
				AddEdge(Idx[i + 1][j], Idx[i][j], v3);
			}
			if (j < m)
			{
				v3 = Wk[i][j][2] + Lk[i][j][2];
				AddEdge(Idx[i][j], Idx[i][j + 1], v3);
				AddEdge(Idx[i][j + 1], Idx[i][j], v3);
			}
		}
	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);
	Sum -= MaxFlow >> 1;
	printf("%d\n", Sum);
	return 0;
}