题解 P4313 【文理分科】
为人民服务
·
·
题解
题目背景
2018年6月6日，明天就是高考，在此提前预祝各位OIers不论文科生，理科生高考都取得好成绩，文综，理综做的顺心。
最后祝愿各位会的都对，蒙的都对，并送上一句名言。
** _经历了这么多痛苦的折磨，变得坚强，而与世隔绝的灵魂里消逝，为什么我枯竭的活力又获得了生命，那是因为明朗的月夜，紧随漆黑的长夜；那是因为和煦的东风，离不开繁枝茂叶；那是因为春天终于来临，冬天终于过去。_ **
——雨果《看，乌云将倾盆大雨泼向这棵树》
**必备知识**
网络流及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**
```cpp
#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;
}
```