自动搬运

查看原文

来自洛谷，原作者为

	为人民服务 **

搬运于2025-08-24 21:58:52，当前版本为作者最后更新于2018-06-06 20:37:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目背景

2018年6月6日，明天就是高考，在此提前预祝各位OIers不论文科生，理科生高考都取得好成绩，文综，理综做的顺心。

$QwQ$，只是在下一个山东高一新生，取代文理分科纠结的是六选三的 $C^3_6$.

最后祝愿各位会的都对，蒙的都对，并送上一句名言。

** 经历了这么多痛苦的折磨，变得坚强，而与世隔绝的灵魂里消逝，为什么我枯竭的活力又获得了生命，那是因为明朗的月夜，紧随漆黑的长夜；那是因为和煦的东风，离不开繁枝茂叶；那是因为春天终于来临，冬天终于过去。 **

			——雨果《看，乌云将倾盆大雨泼向这棵树》

必备知识

网络流及dinic算法

最大流最小割定理

题目分析

回归正题。

这个题很明显是一个最小割好题。但做的人怎么这么少？

我们把每一个人视作一个点 $i$，规定：$i$被割到$S$集里，代表这个人选文，$i$被割到$T$集里，代表这个人选理.

将$S$连向这个点，长度为art，如果该边被割，则说明不选文，不能获得art的收益，可得到science的收益。

将这个点连向$T$，长度为science，如果该边被割，则说明不选理，不能获得science的收益，可得到art的收益。

那么对于同时选择的情况，我们可以新建点。

对于几个相邻的点，我们新建一个点，将$S$连向这个点，长度为同时选文可获得的收益，如果该边被割，则说明这些人不同时选文，不能获得同时选文可获得的收益。

同样，我们新建一个点，将这个点连向$T$，长度为同时选理可获得的收益，如果该边被割，则说明这些人不同时选理，不能获得同时选理可获得的收益，

怎么保证不割这条边则必然都选同样的科目呢？

我们可以将新建的点，向相邻的那几个点中的每一个点（或从相邻的那几个点中的每一个点向新建的点）连一条长度为$inf$的边，这样的边在最小割中肯定不会存在，则保证了在代表共同选择收益的边不被割时（即都选一个科目）新建的点与相邻的点在同一个点集。问题得以解决。

通过Dinic算法求得该图的最小割，总收益减最小割即为最大收益。

论证完毕。

建图方式

把每一个人视作一个点 $i$。

将$S$连向这个点，长度为art。

将这个点连向$T$，长度为science。

新建点，将$S$连向这个点，长度为同时选文可获得的收益，并向相邻的那几个点中的每一个点连一条长度为$inf$的边。

新建点，将这个点连向$T$，长度为同时选理可获得的收益，从相邻的那几个点中的每一个点向新建的点连一条长度为$inf$的边。

Code

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#define Maxn 40001<<1
#define inf (unsigned)-1>>1
using namespace std;

int N,M;int S,T,sum,opt;
const int dx[6]={0,0,0,-1,1};
const int dy[6]={0,-1,1,0,0};
struct Edge {
	int v,flow,rev;
};
inline int read () {
    int X=0,w=1;char ch=0;
    while (ch<'0'||ch>'9')		{ if(ch=='-')	w=-1;ch=getchar(); }
    while (ch>='0'&&ch<='9')	{ X=(X<<1)+(X<<3)+ch-'0';ch=getchar(); }
    return X*w;
}
struct Graph {
	vector <Edge> e[Maxn];queue <int> Q;
	int level[Maxn];
	inline void addedge (int x,int y,int z) {
		e[x].push_back( (Edge){	y,z,e[y].size() } );
		e[y].push_back( (Edge){	x,0,e[x].size()-1} );
	}
	inline bool bfs () {
		memset(level,0,sizeof(level));
		Q.push(S);level[S]=1;
		while(!Q.empty()) {
			int u=Q.front();Q.pop();
			for(int i=0;i<e[u].size();i++) {
				int v=e[u][i].v;
				if( !level[v] && e[u][i].flow ) {
					level[v]=level[u]+1;
					Q.push(v);
				}
			}
		}
		return level[T];
	}
	int dfs (int x,int maxf) {
		if( x==T || maxf==0 )   return maxf;
		int pos=0;
		for(int i=0;i<e[x].size();i++) {
			int v=e[x][i].v;
			if( e[x][i].flow && level[v]==level[x]+1) {
				int f=dfs(v,min(e[x][i].flow,maxf));
				e[x][i].flow-=f;
				e[v][e[x][i].rev].flow+=f;
				pos+=f;
				maxf-=f;
			}
		}
		return pos;
	}
	inline int dinic () {
		int ans=0;
		while(bfs())    ans+=dfs(S,inf);
		return ans;
	}
} G ;
inline int getID (int i,int j) {
	return (i-1)*M+j;
}
int main () {
	N=read();M=read();S=0;T=N*M+1;opt=N*M+1;
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++) {
			int art=read(),id=getID(i,j);
			sum+=art;
			G.addedge(S,id,art);
		}
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++) {
			int science=read(),id=getID(i,j);
			sum+=science;
			G.addedge(id,T,science);
		}
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++) {
			int same_art=read(),id=getID(i,j);opt++;
			sum+=same_art;
			G.addedge(S,opt,same_art);
			G.addedge(opt,id,inf);
			for(int k=1;k<=4;k++)
				if( i+dx[k]>=1 && i+dx[k]<=N && j+dy[k]>=1 && j+dy[k]<=M )
					G.addedge(opt,getID(i+dx[k],j+dy[k]),inf);
		}
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++) {
			int same_science=read(),id=getID(i,j);opt++;
			sum+=same_science;
			G.addedge(opt,T,same_science);
			G.addedge(id,opt,inf);
			for(int k=1;k<=4;k++)
				if( i+dx[k]>=1 && i+dx[k]<=N && j+dy[k]>=1 && j+dy[k]<=M )
					G.addedge(getID(i+dx[k],j+dy[k]),opt,inf);
		}
	printf("%d\n",sum-G.dinic());
	return 0;
}