题目链接
description
太长了,还是自己看题目链接吧.(逃)
solution:
最小割好题.对于每个人,我们可以将其拆点拆为两部分:本身的贡献和额外的贡献,对于每部分连向超级源点的边为选文的贡献,连向超级汇点的边为选理的贡献,然后从第一部分文流向第二部分理,第二部分文流向第一部分理即可.然后用总值减去最小割即可.
(某个傻X作者由于汇点写成源点调了一个下午bug交了二十次全WA正自闭中.)
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#define R register
#define next kdjadskfj
#define debug puts("mlg")
#define mod 1000000009
#define Mod(x) ((x%mod+mod)%mod)
//#define pos(i,j) ((((i-1)*m)+j))
//#define pos1(i,j) ((pos(i,j)+11000))
//#define pos2(i,j) ((pos1(i,j)+22000))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
inline ll read();
inline void write(ll x);
inline void writeln(ll x);
inline void writesp(ll x);
ll n,m,ans,sum;
ll head[2100000],c[2100000],tot=1,next[2100000],to[2100000];
ll S,T;
ll d[1400000];
queue<ll>q;
inline ll pos(ll i,ll j){return (i-1)*m+j;}
inline ll pos1(ll i,ll j){return pos(i,j)+n*m;}
inline ll pos2(ll i,ll j){return pos1(i,j)+n*m;}
inline void add(ll x,ll y,ll u){to[++tot]=y;next[tot]=head[x];head[x]=tot;c[tot]=u;}
inline void Link(ll x,ll y,ll u){add(x,y,u);add(y,x,0);}
bool bfs(){
memset(d,0,sizeof d);
while(!q.empty())q.pop();
q.push(S);d[S]=1;
while(!q.empty()){
ll x=q.front();
q.pop();
for(R ll i=head[x],ver;i;i=next[i]){
ver=to[i];
if(!d[ver]&&c[i]){
q.push(ver);
d[ver]=d[x]+1;
if(ver==T) return true;
}
}
}
return false;
}
ll dinic(ll x,ll flow){
if(x==T||!flow) return flow;
ll rest=flow,k;
for(R ll i=head[x],ver;i&&rest;i=next[i]){
ver=to[i];
if(d[ver]==d[x]+1&&c[i]){
k=dinic(ver,min(c[i],rest));
if(!k) d[ver]=0;
rest-=k;
c[i]-=k;
c[i^1]+=k;
}
}
return flow-rest;
}
int main(){
n=read();m=read();
S=n*m*3+1;T=n*m*3+2;
for(R ll i=1,x;i<=n;i++){
for(R ll j=1;j<=m;j++){
x=read();
ans+=x;
Link(S,pos(i,j),x);
}
}
for(R ll i=1,x;i<=n;i++){
for(R ll j=1;j<=m;j++){
x=read();
ans+=x;
Link(pos(i,j),T,x);
}
}
for(R ll i=1,x;i<n;i++){
for(R ll j=1;j<=m;j++){
x=read();
ans+=x;
Link(S,pos1(i,j),x);
Link(pos1(i,j),pos(i,j),x);
Link(pos1(i,j),pos(i+1,j),x);
}
}
for(R ll i=1,x;i<n;i++){
for(R ll j=1;j<=m;j++){
x=read();
ans+=x;
Link(pos2(i,j),T,x);
Link(pos(i,j),pos2(i,j),x);
Link(pos(i+1,j),pos2(i,j),x);
}
}
for(R ll i=1,x;i<=n;i++){
for(R ll j=1;j<m;j++){
x=read();
ans+=x;
Link(S,pos1(i,j),x);
Link(pos1(i,j),pos(i,j),x);
Link(pos1(i,j),pos(i,j+1),x);
}
}
for(R ll i=1,x;i<=n;i++){
for(R ll j=1;j<m;j++){
x=read();
ans+=x;
Link(pos2(i,j),T,x);
Link(pos(i,j),pos2(i,j),x);
Link(pos(i,j+1),pos2(i,j),x);
}
}
ll _flow;
while(bfs()){
while(_flow=dinic(S,(((ull)1<<62)))) sum+=_flow;
}
write(ans-sum);
}
inline ll read(){ll x=0,t=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*t;}
inline void write(ll x){if(x<0){putchar('-');x=-x;}if(x<=9){putchar(x+'0');return;}write(x/10);putchar(x%10+'0');}
inline void writesp(ll x){write(x);putchar(' ');}
inline void writeln(ll x){write(x);putchar('
');}