Description
文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠
结过）
小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行
描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择
一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式
得到：
1．如果第i行第秒J的同学选择了文科，则他将获得art[i][j]的满意值，如
果选择理科，将得到science[i][j]的满意值。
2．如果第i行第J列的同学选择了文科，并且他相邻（两个格子相邻当且
仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开
心，所以会增加same_art[i][j]的满意值。
3．如果第i行第j列的同学选择了理科，并且他相邻的同学全部选择了理
科，则增加same_science[i]j[]的满意值。
小P想知道，大家应该如何选择，才能使所有人的满意值之和最大。请
告诉他这个最大值。
Input
第一行为两个正整数：n，m
接下来n术m个整数，表示art[i][j]；
接下来n术m个整数．表示science[i][j]；
接下来n术m个整数，表示same_art[i][j]；
Output
输出为一个整数，表示最大的满意值之和
Sample Input
3 4
13 2 4 13
7 13 8 12
18 17 0 58 13 15 4
11 3 8 11
11 18 6 51 2 3 4
4 2 3 2
3 1 0 4
3 2 3 2
0 2 2 1
0 2 4 4
Sample Output
152
HINT
样例说明
1表示选择文科，0表示选择理科，方案如下：
1 0 0 1
0 1 0 0
1 0 0 0
N,M<=100,读入数据均<=500
/**************************************************************
Problem: 3894
User: ictsing
Language: C++
Result: Accepted
Time:1540 ms
Memory:8324 kb
****************************************************************/
//3894: 文理分科
/*
最大权闭合子图：
有一个有向图，点权可以为正也可以为负。选一个点集，
如果点中所有的点连接的边都出现在这个点集中，那就中闭合图。
如果点权和最大就是最大权闭合子图。
二元组建图：
1.一个简单的问题
n个任务，每个任务在机器a中花费ai，在机器b中花费bi
m对关系(x,y)->x和y不在同一个机器上完成，那么增加v的花费
我们可以转化问题得到：
x
/ | \
ax | bx
/ | \
s v t
\ | /
ay | by
\ | /
y
发现四个情况一一对应：
1.同时在a完成，需要割掉与s相连的边，花费ax+ay
2.同时在a完成，需要割掉与t相连的边，花费bx+by
3.如果a完成x，b完成y,需要割掉x,y相连的边，花费ax+by+v
4.如果a完成y，b完成x,需要割掉x,y相连的边，花费bx+ay+v
2.问题一般化：
n个任务，每个任务在机器a中花费ai，在机器b中花费bi
m对关系(x,y)->
x,y同时在a上完成，v1[xy]
x,y同时在b上完成，v2[xy]
x在a上完成,y在b上完成，v3[xy]
x在b上完成,y在a上完成，v4[xy]
x
/ | \
a | c
/ | \
s ⬇️e(f⬆️) t
\ | /
b | d
\ | /
y
a+b=v1
c+d=v2
a+d+f=v3
b+c+e=v4
为了满足最小割的定义，
我们要做的就是a,b,c,d,e,f≥0{均}
我们发现：
a,c选择且仅一个
d,b选择且仅一个
若a,c<0,那么我们均+w使其为正,求最小割掉，再-w也是可行的
若d,b<0,那么同理
所以e,f≥0
后来可以得出,
f+e=v3+v4-v1-v2=k≥0,
我们把两条有向边转化为无向边f=e=k/2
k<0怎么办：
我们可以换一个假设：
x
/ | \
bx | ax
/ | \
s e t
\ | /
ay | by
\ | /
y
a+b=v4
c+d=v3
a+d+e=v2
b+c+e=v1
2e=v1+ v2-v4-v3=-k
若k<0,我们这样建图就可以满足条件了
但是这个方法有一个前提，
若某一组(x,y)的k值小于0，
则x,y不能以同一种方式与s，t相连，
将x,y相连要保证图中不能出现奇环（即一定是二分图）
然后这道题怎么搞呢？
1.首先如果熟悉最大权闭合子图的话
肯定能想到：总收益减去最小代价
2.利用二元组思路，
我们考虑对于额外的收入，加入一个新的点
x表示一个学生，与S连通表示学文，
与T连通表示学理。y表示新加的点，用来计算同时学理的额外收益，与S连通表示不
要额外收益，与T连通表示要额外收益先算出总收益，再用最小割减去即可
x
/ | \
a | c
/ | \
s ⬇️e(f⬆️) t
\ | /
b | d
\ | /
y
c+d=B[i]+WB(学生i学文，不要额外收益，损失学理收益，损失额外收益)
a+b=A[i](学生i学理，要额外收益，损失学文收益)
b+f+c=inf(学生i学文，要额外收益)
a+e+d=A[i]+WB（学生学理，不要额外收益，损失学文收益，损失学理额外收益）
a=A[i]
b=0
c=B[i]
d=WB
e=0
f=inf
同时学文类似，只是方向不同，收益不同。
*/
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int ecnt =1;
const int mt = 2e5+5;//(50+1)*(50+1)*(2+2+10);
const int inf = 1e9;
int to[mt<<1],nxt[mt<<1],cap[mt<<1],cur[mt],lev[mt],adj[mt];
void adde(int a,int b,int c)
{
ecnt++,to[ecnt]=b,nxt[ecnt]=adj[a],cap[ecnt]=c,adj[a]=ecnt;
//cout<<ecnt<<" "<<to[ecnt]<<" "<<nxt[ecnt]<<" "<<cap[ecnt]<<" "<<adj[ecnt]<<endl;
}
int n,m;
int id(int x,int y)
{
return (x-1)*m+y;//竟然打成了n，我可能真的是智障
}
queue<int>q;
int s,t;
bool bfs()
{
while(!q.empty()) q.pop();
for(int i=0;i<mt;i++) lev[i]=-1,cur[i]=adj[i];
q.push(s),lev[s]=0;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=adj[u];i;i=nxt[i])
{
int v=to[i];
if(lev[v]==-1&&cap[i]>0)
{
lev[v]=lev[u]+1;
q.push(v);
if(v==t) return true;
}
}
}
return false;
}
int dinic(int u,int flow)
{
if(u==t) return flow;
int delta,res=0;
for(int &i=cur[u];i;i=nxt[i])
{
int v=to[i];
if(cap[i]>0&&lev[v]>lev[u])
{
delta=dinic(v,min(cap[i],flow-res));
if(delta)
{
cap[i]-=delta,cap[i^1]+=delta,res+=delta;
if(res==flow) break;
}
}
}
if(res!=flow) lev[u]=-1;
return res;
}
int mincut()
{
int ret=0;
while(bfs()) ret+=dinic(s,inf);
return ret;
}
inline int read()
{
int num=0,flag=1;
char ch;
do{
ch=getchar();
if(ch=='-') flag=-1;
}while(ch<'0'||ch>'9');
do{
num=num*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return num*flag;
}
int main()
{
n=read(),m=read();
int ans=0;
int a;
s=0,t=n*m+3+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a=read(),adde(s,id(i,j),a),adde(id(i,j),s,0),ans+=a;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a=read(),adde(id(i,j),t,a),adde(t,id(i,j),0),ans+=a;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int qaq=read();
int k=id(i,j)+n*m;
ans+=qaq;
adde(s,k,qaq),adde(k,s,0);
adde(k,id(i,j),inf),adde(id(i,j),k,0);
if(i-1>=1) adde(k,id(i-1,j),inf),adde(id(i-1,j),k,0);
if(j+1<=m) adde(k,id(i,j+1),inf),adde(id(i,j+1),k,0);
if(j-1>=1) adde(k,id(i,j-1),inf),adde(id(i,j-1),k,0);
if(i+1<=n) adde(k,id(i+1,j),inf),adde(id(i+1,j),k,0);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int qaq=read();
int k=id(i,j)+n*m*2;
ans+=qaq;
adde(k,t,qaq),adde(t,k,0);
adde(id(i,j),k,inf),adde(k,id(i,j),0);
if(i-1>=1) adde(id(i-1,j),k,inf),adde(k,id(i-1,j),0);
if(j+1<=m) adde(id(i,j+1),k,inf),adde(k,id(i,j+1),0);
if(j-1>=1) adde(id(i,j-1),k,inf),adde(k,id(i,j-1),0);
if(i+1<=n) adde(id(i+1,j),k,inf),adde(k,id(i+1,j),0);
}
// cout<<ans<<endl;
printf("%d\n",ans-mincut());
return 0;
}
评论