文理分科（最大流最小割定理）

传送门

数据范围一眼网络流。

考虑每个人文理只能选一个，考虑最小割。

考虑源点\(S\)向\((i,j)\)连一条费用为\(art_{i,j}\)的边，\((i,j)\)向汇点\(T\)连一条费用为\(science_{i,j}\)的边。若割\(S\)与\((i,j)\)的边，则表示\((i,j)\)不选文，若割\((i,j_\)与\(T\)的边，则表示\((i,j)\)不选理。

然后考虑相邻的人都选文的情况，新建一个点\(cnt\)，不妨设这个\(cnt\)表示\((i,j)\)及\((i,j)\)相邻的人都选了文的情况，则源点\(S\)向\(cnt\)连一条\(same_art_{i,j}\)的边，\(cnt\)分别向向\((i,j),(i+1,j),(i-1,j),(i,j+1),(i,j-1)\)连一条费用为\(inf\)的边，若割掉源点\(S\)与\(cnt\)的边，表示这五个不全选文

相邻的人选理的情况同理，只不过是向汇点连罢了。

上代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=3e5+50,hd=1e9,INF=1e15;
ll n,m,zh,s,t,sr,cnt,ans;
ll h[N],e[N],ne[N],w[N],idx=1;
void add(ll a,ll b,ll c)
{
	e[++idx]=b;
	w[idx]=c;
	ne[idx]=h[a];
	h[a]=idx;
	e[++idx]=a;
	w[idx]=0;
	ne[idx]=h[b];
	h[b]=idx; 
}
ll dep[N],now[N];
bool bfs()
{
	for(ll i=0;i<=cnt;i++) dep[i]=INF;
	dep[s]=1;
	queue<ll> q;
	q.push(s);
	now[s]=h[s];
	while(!q.empty())
	{
		ll wz=q.front();
		q.pop();
		for(ll i=h[wz];i;i=ne[i])
		{
			ll j=e[i];
			if(w[i]==0) continue;
			if(dep[j]==INF)
			{
				now[j]=h[j];
				dep[j]=dep[wz]+1;
				q.push(j);
				if(j==t) return true;
			}
		}
	}
	return false;
}
ll dfs(ll wz,ll k)
{
	if(wz==t) return k;
	ll sum,res=0;
	for(ll i=now[wz];i&&k;i=ne[i])
	{
		now[wz]=i;
		ll j=e[i];
		if(w[i]==0||dep[j]!=dep[wz]+1) continue;
		sum=dfs(j,min(k,w[i]));
		if(sum==0) dep[j]=INF;
		res+=sum;
		k-=sum;
		w[i]-=sum;
		w[i^1]+=sum;
	}
	return res;
}
int main()
{
	scanf("%lld %lld",&n,&m);
	s=0,t=1,cnt=n*m+1;
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=m;j++)
		{
			scanf("%lld",&sr);
			zh+=sr;
			add(s,(i-1)*m+j+1,sr); 
		}
	}
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=m;j++)
		{
			scanf("%lld",&sr);
			zh+=sr;
			add((i-1)*m+j+1,t,sr);
		}
	}
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=m;j++)
		{
			scanf("%lld",&sr);
			zh+=sr;
			cnt++;
			add(s,cnt,sr);
			add(cnt,(i-1)*m+j+1,sr);
			if(i!=1) add(cnt,(i-2)*m+j+1,hd);
			if(i!=n) add(cnt,i*m+j+1,hd);
			if(j!=1) add(cnt,(i-1)*m+j,hd);
			if(j!=m) add(cnt,(i-1)*m+j+2,hd);
		}
	}
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=m;j++)
		{
			scanf("%lld",&sr);
			zh+=sr;
			cnt++;
			add(cnt,t,sr);
			add((i-1)*m+j+1,cnt,sr);
			if(i!=1) add((i-2)*m+j+1,cnt,hd);
			if(i!=n) add(i*m+j+1,cnt,hd);
			if(j!=1) add((i-1)*m+j,cnt,hd);
			if(j!=m) add((i-1)*m+j+2,cnt,hd);
		}
	}
	while(bfs()) ans+=dfs(s,INF);
	printf("%lld\n",zh-ans);
	return 0;
}