显示代码纯文本
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define maxn 10005
#define maxx 130005
#define maxa 105
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,m,edge,hea[maxn],num,cnt,dis[maxn],st,ed,inf=0x7fffffff,sum,wr[maxa][maxa],bwr[maxa][maxa],cwr[maxa][maxa],ma[maxa][maxa],bma[maxa][maxa],cma[maxa][maxa];
inline int read()
{ char c=getchar();int x=0,y=1;
while(c<'0'||c>'9'){if(c=='-') y=-1; c=getchar();}
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*y;
}
struct road{int en,cap,nex;}ro[maxx];
void add(int x,int y,int z)
{
ro[num].en=y;ro[num].cap=z;ro[num].nex=hea[x];hea[x]=num++;
ro[num].en=x;ro[num].cap=0;ro[num].nex=hea[y];hea[y]=num++;
}
bool bfs(int s,int t)
{
queue<int>q;mem(dis,0);
q.push(s);dis[s]=1;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=hea[u];i!=-1;i=ro[i].nex)
{
int v=ro[i].en;
if(!dis[v]&&ro[i].cap){dis[v]=dis[u]+1;q.push(v);if(v==t) return 1;}
}
}
return 0;
}
int dfs(int x,int y,int z)
{
if(x==y) return z;
int f,tmp=0;
for(int i=hea[x];i!=-1;i=ro[i].nex)
{
int v=ro[i].en;
if((dis[v]==dis[x]+1)&&ro[i].cap)
{
f=dfs(v,y,min(z-tmp,ro[i].cap));
if(!f){dis[v]=0;continue;}
ro[i].cap-=f;ro[i^1].cap+=f;
tmp+=f;
if(tmp==z) return tmp;
}
}
return tmp;
}
void dinic(int s,int t)
{
int ans=0;
while(bfs(s,t)) ans+=dfs(s,t,inf);
printf("%d",sum-(ans>>1));
}
int main()
{
freopen("nt2011_happiness.in","r",stdin);
freopen("nt2011_happiness.out","w",stdout);
mem(hea,-1);
n=read();m=read();
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) wr[i][j]=read(),sum+=wr[i][j];
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ma[i][j]=read(),sum+=ma[i][j];
for(int i=1;i<n;i++) for(int j=1;j<=m;j++) bwr[i][j]=read(),sum+=bwr[i][j];
for(int i=1;i<n;i++) for(int j=1;j<=m;j++) bma[i][j]=read(),sum+=bma[i][j];
for(int i=1;i<=n;i++) for(int j=1;j<m;j++) cwr[i][j]=read(),sum+=cwr[i][j];
for(int i=1;i<=n;i++) for(int j=1;j<m;j++) cma[i][j]=read(),sum+=cma[i][j];
ed=n*m+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int tmp=(i-1)*m+j;
add(st,tmp,(wr[i][j]<<1)+bwr[i][j]+cwr[i][j]+bwr[i-1][j]+cwr[i][j-1]);
add(tmp,ed,(ma[i][j]<<1)+bma[i][j]+cma[i][j]+bma[i-1][j]+cma[i][j-1]);
if(i<n) add(tmp,tmp+m,bwr[i][j]+bma[i][j]);
if(i>1) add(tmp,tmp-m,bwr[i-1][j]+bma[i-1][j]);
if(j>1) add(tmp,tmp-1,cwr[i][j-1]+cma[i][j-1]);
if(j<m) add(tmp,tmp+1,cwr[i][j]+cma[i][j]);
}
dinic(st,ed);
return 0;
}
Anonymity