P4313文理分科
记录
dicnic

#include <cstdio>
#include <queue>
#include <cstring>
#define int long long 
using namespace std;
const int N = 100010,M = 2000010,INF = 2e9;
int n,m,tmp,a,b,p,sum,ans,tot = 1,S,T,dep[N],head[N],to[M],val[M],nxt[M];
int dx[5] = {-1,0,1,0,0},dy[5] = {0,1,0,-1,0};
queue <int> q;
int id(int x,int y){return (x - 1) * m + y;}
void add_(int x,int y,int z)
{
	tot++;
	to[tot] = y,val[tot] = z;
	nxt[tot] = head[x],head[x] = tot;
}
bool bfs()
{
	memset(dep,0,sizeof(dep));
	dep[S] = 1;
	q.push(S);
	while(!q.empty())
	{
		a = q.front(),q.pop();
		for(int i = head[a];i;i = nxt[i])
		{
			b = to[i];
			if(!val[i] || dep[b]) continue;
			dep[b] = dep[a] + 1;
			q.push(b);
		}
	}
	return (dep[T] > 0);
}
int dfs(int x,int f)
{
	if(x == T || !f) return f;
	int tmp,ret = 0,y;
	for(int i = head[x];i && f;i = nxt[i])
	{
		y = to[i];
		if(dep[y] != dep[x] + 1 || !val[i]) continue;
		tmp = dfs(y,min(f,val[i]));
		ret += tmp;
		f -= tmp;
		val[i] -= tmp;
		val[i ^ 1] += tmp;
	}
	if(ret == 0) dep[x] = 0;
	return ret;
}
signed main()
{
	memset(head,0,sizeof(head));
	ans = sum = 0;
	scanf("%lld%lld",&n,&m);
	S = 0,T = 3 * n * m + 1;
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
		{
			scanf("%lld",&tmp);
			sum += tmp;
			add_(S,id(i,j),tmp);
			add_(id(i,j),S,0);
		}
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
		{
			scanf("%lld",&tmp);
			sum += tmp;
			add_(id(i,j),T,tmp);
			add_(T,id(i,j),0);
		}
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
		{
			scanf("%lld",&tmp);
			sum += tmp;
			p = n * m + id(i,j);
			add_(S,p,tmp);
			add_(p,S,0);
			for(int k = 0,nx,ny;k < 5;k++)
			{
				nx = i + dx[k],ny = j + dy[k];
				if(nx < 0 || nx > n || ny < 0 || ny > m) continue;
				add_(p,id(nx,ny),INF);
				add_(id(nx,ny),p,0);
			}
		}
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
		{
			scanf("%lld",&tmp);
			sum += tmp;
			p = 2 * n * m + id(i,j);
			add_(p,T,tmp);
			add_(T,p,0);
			for(int k = 0,nx,ny;k < 5;k++)
			{
				nx = i + dx[k],ny = j + dy[k];
				if(nx < 0 || nx > n || ny < 0 || ny > m) continue;
				add_(id(nx,ny),p,INF);
				add_(p,id(nx,ny),0);
			}
		}
	while(bfs()) ans += dfs(S,INF);
	printf("%lld\n",sum - ans);
	return 0;
}