http://www.lydsy.com/JudgeOnline/problem.php?id=3774
tm这最小割能考到这么变态是一种境界
//#define _TEST _TEST #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #include <algorithm> using namespace std; /************************************************ Code By willinglive Blog:http://willinglive.cf ************************************************/ #define rep(i,l,r) for(int i=(l),___t=(r);i<=___t;i++) #define per(i,r,l) for(int i=(r),___t=(l);i>=___t;i--) #define MS(arr,x) memset(arr,x,sizeof(arr)) #define LL long long #define INE(i,u,e) for(int i=head[u];~i;i=e[i].next) inline const int read() {int r=0,k=1;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1; for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';return k*r;} ///////////////////////////////////////////////// const int inf=0x3f3f3f3f; const int N=6000; const int M=8*N; int n,m; int a[51][51],b[51][51]; struct edge{int v,flow,cap,next;}e[M]; int head[N],k; int S,T; int cur[N],d[N],q[N]; int di[]={0,0,1,-1}; int dj[]={1,-1,0,0}; ///////////////////////////////////////////////// inline int enc(int x,int y,bool b){return ((x-1)*m+y)<<1|b;} void adde(int u,int v,int f){e[k].v=v;e[k].flow=0;e[k].cap=f;e[k].next=head[u];head[u]=k++;} void ins(int u,int v,int f1,int f2){adde(u,v,f1);adde(v,u,f2);} inline int F(int i){return e[i].cap-e[i].flow;} bool bfs() { MS(d,-1); d[q[0]=S]=0; memcpy(cur,head,sizeof(cur)); for(int u,v,l=0,r=1;l<r;) { u=q[l++]; INE(i,u,e) if(F(i)&&d[v=e[i].v]==-1) { q[r++]=v; d[v]=d[u]+1; if(v==T) return 1; } } return 0; } int dfs(int u,int a) { if(u==T||a==0) return a; for(int &i=cur[u];~i;i=e[i].next) if(F(i)&&d[e[i].v]==d[u]+1) { if(int t=dfs(e[i].v,min(a,F(i)))) { e[i].flow+=t; e[i^1].flow-=t; return t; } } return 0; } int dinic() { int f=0; while(bfs()) while(int t=dfs(S,inf)) f+=t; return f; } ///////////////////////////////////////////////// void input() { MS(head,-1); n=read(); m=read(); rep(i,1,n) rep(j,1,m) a[i][j]=read(); rep(i,1,n) rep(j,1,m) b[i][j]=read(); } void solve() { S=enc(n,m,1)+1; T=S+1; rep(i,1,n) rep(j,1,m) { if((i+j)&1) { ins(S,enc(i,j,0),a[i][j],0); ins(enc(i,j,0),enc(i,j,1),b[i][j],0); } else { ins(enc(i,j,0),T,a[i][j],0); ins(enc(i,j,1),enc(i,j,0),b[i][j],0); } rep(k,0,3) { int ni=i+di[k],nj=j+dj[k]; if(ni<1||ni>n||nj<1||nj>m) continue; if((i+j)&1) ins(enc(i,j,1),enc(ni,nj,0),inf,0); else ins(enc(ni,nj,0),enc(i,j,1),inf,0); } } int s=0; rep(i,1,n) rep(j,1,m) s+=b[i][j]; cout<<s-dinic()<<endl; } ///////////////////////////////////////////////// int main() { #ifndef _TEST freopen("std.in","r",stdin); freopen("std.out","w",stdout); #endif input(),solve(); return 0; }