蒟蒻在把点拆成文科理科,然后连了一条无穷大的边,为什么要建双向的才能AC(我看题解好像都没拆开,但我觉得我这样不是没错吗?) 代码如下

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn = 1e6 + 10;
struct Edge{
	int nxt,point,flow;
}edge[maxn<<1];
int S,T,dep[maxn],cur[maxn],head[maxn],q[maxn],tot;
void add(int x,int y,int flow){
	edge[++tot].nxt = head[x];edge[tot].point = y;edge[tot].flow = flow;head[x] = tot;
	edge[++tot].nxt = head[y];edge[tot].point = x;edge[tot].flow = 0;	head[y] = tot;
}
bool bfs(){
	for(int i = S; i <= T; ++i)		cur[i] = head[i],dep[i] = 0;
	dep[S] = 1;
	int l = 1,r = 0;
	q[++r] = S;
	while(l <= r){
		int x = q[l++];
		for(int i = head[x]; i ; i = edge[i].nxt){
			int y = edge[i].point;
			if(!dep[y] && edge[i].flow){
				dep[y] = dep[x] + 1;
				q[++r] = y;
			}
		}
	}
	return (dep[T] != 0);
}
int Dinic(int x,int flow){
	if(x == T || !flow)	return flow;
	int rest = flow,k;
	for(int i = cur[x]; i ; i = edge[i].nxt){
		int y = edge[i].point;
		cur[x] = i;
		if(edge[i].flow && dep[y] == dep[x] + 1){
			k = Dinic(y,min(edge[i].flow,rest));
			if(!k)	dep[y] = 0;
			rest -= k;
			edge[i].flow -= k;
			edge[i^1].flow += k;
		}
	}
	return flow - rest;
}
int n,m;
int id[510][510][4],idcnt = 0;
int ans = 0;
int read(){
	char c = getchar();
	int x = 0;
	while(c < '0' || c > '9')		c = getchar();
	while(c >= '0' && c <= '9')		x = x * 10 + c - 48,c = getchar();
	return x;
}
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
bool check(int x,int y){
	return (x >= 1 && x <= n && y >= 1 && y <= m);
}
int a[510][510],b[510][510],c[510][510],d[510][510];
void getdata(int a[510][510]){
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)		a[i][j] = read(),ans += a[i][j];
}
int main(){
	tot = 1;
	n = read(),m = read();
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
		id[i][j][0] = ++idcnt,id[i][j][1] = ++idcnt,id[i][j][2] = ++idcnt,id[i][j][3] = ++idcnt;
	getdata(a);getdata(b);getdata(c);getdata(d);
	T = ++idcnt;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			add(S,id[i][j][0],a[i][j]);/*文科*/
			add(S,id[i][j][2],c[i][j]);
			add(id[i][j][1],T,b[i][j]);/*理科*/
			add(id[i][j][3],T,d[i][j]);
			add(id[i][j][0],id[i][j][1],1e9);
			add(id[i][j][1],id[i][j][0],1e9);/*为什么要建双向边*/ 
		}
	}
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			add(id[i][j][2],id[i][j][1],1e9);
			add(id[i][j][0],id[i][j][3],1e9);
			for(int k = 0; k < 4; ++k){
				int u = i + dx[k],v = j + dy[k];
				if(!check(u,v))	continue;
				add(id[i][j][2],id[u][v][1],1e9);
				add(id[u][v][0],id[i][j][3],1e9);
			} 
		}
	} 
	while(bfs())	ans -= Dinic(S,1e9);
	cout<<ans<<endl;
	return 0;
}