记录编号	431092	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]happiness(吴确)	最终得分	100
用户昵称	Hzoi_moyi	是否通过	通过
代码语言	C++	运行时间	0.329 s
提交时间	2017-07-31 09:16:13	内存使用	1.87 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int sj=105;
int n,m,sx[sj][sj],e,h[sj*sj],s,t,dep[sj*sj];
int w[sj][sj],l[sj][sj],g[sj][sj],z[sj][sj],a1,ans;
struct B
{
    int ne,v,w;
}b[sj*sj*10];
queue<int> q;
void add(int x,int y,int z)
{
     b[e].v=y;
     b[e].w=z;
     b[e].ne=h[x];
     h[x]=e++;
}
/*int r()
{
    int jg=0,jk=0;
    jk=getchar()-'0';
    if(jk>=0&&jk<=9)  jg+=jk;
    jk=getchar()-'0';
    while(jk<=9&&jk>=0)
    {
       jg*=10;
       jg+=jk;
       jk=getchar()-'0';
    }
    return jg;
}*/
void init()
{
    scanf("%d%d",&n,&m);
    t=n*m+1;
    memset(h,-1,sizeof(h));
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
      {
        scanf("%d",&w[i][j]);
        sx[i][j]=(i-1)*m+j;
        ans+=w[i][j];
        w[i][j]*=2;
      }
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
      {
        scanf("%d",&l[i][j]);
        ans+=l[i][j];
        l[i][j]*=2;
      }
    for(int i=1;i<n;i++)
      for(int j=1;j<=m;j++)
      {
        scanf("%d",&a1);
        ans+=a1;
        g[i][j]=a1;
        w[i][j]+=a1;
        w[i+1][j]+=a1;
      }
    for(int i=1;i<n;i++)
      for(int j=1;j<=m;j++)
      {
        scanf("%d",&a1);
        ans+=a1;
        g[i][j]+=a1;
        l[i][j]+=a1;
        l[i+1][j]+=a1;
        add(sx[i][j],sx[i+1][j],g[i][j]);
        add(sx[i+1][j],sx[i][j],g[i][j]);
      }
    for(int i=1;i<=n;i++)
      for(int j=1;j<m;j++)
      {
        scanf("%d",&a1);
        ans+=a1;
        z[i][j]=a1;
        w[i][j]+=a1;
        w[i][j+1]+=a1;
        add(s,sx[i][j],w[i][j]);
        add(sx[i][j],s,0);
      }
    for(int i=1;i<=n;i++)
    {
      add(s,sx[i][m],w[i][m]);
      add(sx[i][m],s,0);
    }
    for(int i=1;i<=n;i++)
      for(int j=1;j<m;j++)
      {
        scanf("%d",&a1);
        ans+=a1;
        z[i][j]+=a1;
        l[i][j]+=a1;
        l[i][j+1]+=a1;
        add(t,sx[i][j],0);
        add(sx[i][j],t,l[i][j]);
        add(sx[i][j],sx[i][j+1],z[i][j]);
        add(sx[i][j+1],sx[i][j],z[i][j]);
      }
    for(int i=1;i<=n;i++)
    {
      add(sx[i][m],t,l[i][m]);
      add(t,sx[i][m],0);
    }
    ans*=2;
}
bool bfs(int x)
{
    while(!q.empty()) q.pop();
    memset(dep,0,sizeof(dep));
    dep[x]=1;
    q.push(x);
    while(!q.empty())
    {
       x=q.front();
       q.pop();
       for(int i=h[x];i!=-1;i=b[i].ne)
         if(!dep[b[i].v]&&b[i].w)
         {
            dep[b[i].v]=dep[x]+1;
            if(b[i].v==t) return 1;
            q.push(b[i].v);
         }
    }
    return 0;
}
int bj(int x,int y)
{
     return x<y?x:y;
}
int dfs(int x,int f)
{
     if(x==t) return f;
     int ans=0,d;
     for(int i=h[x];i!=-1;i=b[i].ne)
       if(dep[b[i].v]==dep[x]+1&&b[i].w)
       {
          d=dfs(b[i].v,bj(f,b[i].w));
          f-=d;
          ans+=d;
          b[i].w-=d;
          b[i^1].w+=d;
          if(!f) break;
       }
     if(!ans) dep[x]=-1;
     return ans;
}
int main()
{
    //freopen("t.txt","r",stdin);
    freopen("nt2011_happiness.in","r",stdin);
    freopen("nt2011_happiness.out","w",stdout);
    init();
    while(bfs(s))  ans-=dfs(s,0x7fffffff);
    printf("%d",ans/2);
    //while(1);
    return 0;
}