题解 P4313 【文理分科】
jun头吉吉
2020-07-14 14:07:29
# P4313 【文理分科】
[$\color{green}{\text{更好的阅读体验}}$](https://chen-jia-liang.gitee.io/blog/2020/07/14/%E9%A2%98%E8%A7%A3-P4313-%E3%80%90%E6%96%87%E7%90%86%E5%88%86%E7%A7%91%E3%80%91/)
## 题意
每个人选文科或理科可以有满意值，几个人同时选文科或理科也可以获得满意值，求满意值的最大值。
~~??为什么文科是art~~
## 题解
看到这类**二者选其一**的模型，我们肯定能想到**最小割**。首先，我们先从矩阵中拿出小盆友$A$和TA的相邻同学$B$、$C$、$D$、$E$，怼到图上，在画上源点和汇点，分别代表文科和理科：
假设没有额外的快乐值，我们可以这么连边：
如果我们割去一条边，就代表着不选文科/理科，若图不连通，则代表每个点只与源点或汇点联通，**即每个人只选文科或理科**。然后我们再去考虑$same$值，显然，我们如果选了一条$science$的边，就要把$same\ art$删掉；同理，我们如果选了一条$art$的边，就要把$same\ science$删掉，因此，我们可以加上两个虚点，连上边：
建完了图剩下的代码就简单了
## 代码
```cpp
#pragma optimize(2)
#include<bits/stdc++.h>
using namespace std;
namespace in{
char buf[1<<21],*p1=buf,*p2=buf;
inline int getc(){
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}
template <typename T>inline void read(T& t){
t=0;int f=0;char ch=getc();
while (!isdigit(ch)){
if(ch=='-')f = 1;
ch=getc();
}
while(isdigit(ch)){
t=t*10+ch-48;
ch = getc();
}
if(f)t=-t;
}
template <typename T,typename... Args> inline void read(T& t, Args&... args){
read(t);read(args...);
}
}
namespace out{
char buffer[1<<21];
int p1=-1;
const int p2 = (1<<21)-1;
inline void flush() {
fwrite(buffer,1,p1+1,stdout),
p1=-1;
}
inline void putc(const char &x) {
if(p1==p2)flush();
buffer[++p1]=x;
}
template <typename T>void write(T x) {
static char buf[15];
static int len=-1;
if(x>=0){
do{
buf[++len]=x%10+48,x/=10;
}while (x);
}else{
putc('-');
do {
buf[++len]=-(x%10)+48,x/=10;
}while(x);
}
while (len>=0)
putc(buf[len]),--len;
}
}
const int maxn=4000010,maxe=100010*2;
struct Graph{
struct node{
int v,w,nxt;
}e[maxe<<1];
int head[maxn],cur[maxn],tot;
int dis[maxn];
int s,t;
void init(int _s,int _t){s=_s,t=_t;tot=1;memset(head,0,sizeof head);}
Graph(int _s=0,int _t=0){init(_s,_t);}
void add(int u,int v,int w){
//printf("%d %d %d\n",u,v,w);
e[++tot]=(node){v,w,head[u]},head[u]=tot;
e[++tot]=(node){u,0,head[v]},head[v]=tot;
}
#define v e[i].v
inline bool bfs(){
queue<int>q;
memset(dis,0,sizeof dis);
memcpy(cur,head,sizeof head);
dis[s]=1;q.push(s);
while(q.size()){
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt)
if(!dis[v]&&e[i].w){
dis[v]=dis[u]+1,q.push(v);
if(v==t)return true;
}
}
return false;
}
int dfs(int u,int flow){
if(u==t)return flow;
int rest=flow;
for(int i=cur[u];i&&rest;i=e[i].nxt){
if(dis[v]==dis[u]+1&&e[i].w){
int tmp=dfs(v,min(rest,e[i].w));
rest-=tmp,e[i].w-=tmp,e[i^1].w+=tmp;
}
cur[u]=i;
}
if(rest==0)dis[u]=-1;
return flow-rest;
}
#undef v
int dinic(){
int ans=0;
while(bfs())
while(int sth=dfs(s,2e9))
ans+=sth;
return ans;
}
}G;
int n,m,x;
int sum,tot;
bool check(int x,int y){
return x<=n&&x>=1&&y<=m&&y>=1;
}
#define P(i,j) ((i)-1)*m+(j)
signed main(){
//freopen("1.in","r",stdin);
in::read(n,m);
tot=n*m;G.init(0,++tot);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
in::read(x);sum+=x;
G.add(G.s,P(i,j),x);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
in::read(x);sum+=x;
G.add(P(i,j),G.t,x);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
in::read(x);sum+=x;
G.add(G.s,++tot,x);
G.add(tot,P(i,j),1e9);
if(check(i,j-1))G.add(tot,P(i,j-1),1e9);
if(check(i,j+1))G.add(tot,P(i,j+1),1e9);
if(check(i-1,j))G.add(tot,P(i-1,j),1e9);
if(check(i+1,j))G.add(tot,P(i+1,j),1e9);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
in::read(x);sum+=x;
G.add(++tot,G.t,x);
G.add(P(i,j),tot,1e9);
if(check(i,j-1))G.add(P(i,j-1),tot,1e9);
if(check(i,j+1))G.add(P(i,j+1),tot,1e9);
if(check(i-1,j))G.add(P(i-1,j),tot,1e9);
if(check(i+1,j))G.add(P(i+1,j),tot,1e9);
}
out::write(sum-G.dinic());
out::flush();
}
```
## 举一反三
[happiness](https://www.luogu.com.cn/problem/P1646)
[小M的作物](https://www.luogu.com.cn/problem/P1361)