记录编号	56012	评测结果	AAAAAAAAAAA
题目名称	[网络流24题] 方格取数问题	最终得分	100
用户昵称	MikuHatsune	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2013-03-24 19:07:04	内存使用	11.93 MiB

#include <cstdio>
#define L 1000000
#define N 10000
int a[L],tl[N],nx[L],f[L],d[N],o[N],bh[101][101],xf[4]={-1,1,0,0},yf[4]={0,0,-1,1},
    bg,ed,n,m,i,j,ln,t,ans,map[101][101];

void add(int x,int y,int fl)
{
    a[tl[x]=nx[tl[x]]=++ln]=y;
    f[ln]=fl;
    a[tl[y]=nx[tl[y]]=++ln]=x;
    f[ln]=0;
}

int func(int k,int fl)
{
    if (k==ed) return fl;
    int i,t,flow=fl;
    for (i=nx[k]; i!=0; i=nx[i])
    if (f[i]>0 && d[a[i]]==d[k]-1)
    {
        t=func(a[i],((f[i]<fl)?f[i]:fl));
        f[i]-=t; fl-=t;
        if ((i-ed)&1) f[i+1]+=t; else f[i-1]+=t;
        if (d[bg]>ed || fl==0) return flow-fl;
    }
    if (--o[d[k]]==0) d[bg]=ed+1;
    ++o[++d[k]];
    return flow-fl;
}

int main()
{
    freopen("grid.in","r",stdin);
    freopen("grid.out","w",stdout);
    scanf("%d%d",&n,&m);
    bg=n*m+1; ed=bg+1;
    for (i=1; i<=ed; ++i) tl[i]=++ln;
    for (i=1; i<=n; ++i)
    for (j=1; j<=m; ++j)
    {
        scanf("%d",&map[i][j]);
        ans+=map[i][j];
        bh[i][j]=++t;
        if ((i+j)&1) add(bg,t,map[i][j]);
        else add(t,ed,map[i][j]);
    }
    for (i=1; i<=n; ++i)
    for (j=1; j<=m; ++j)
    if ((i+j)&1)
    for (t=0; t<4; ++t)
    if (bh[i+xf[t]][j+yf[t]]!=0) add(bh[i][j],bh[i+xf[t]][j+yf[t]],1000000007);
    o[0]=ed;
    while (d[bg]<=ed) ans-=func(bg,1000000007);
    printf("%d\n",ans);
  //  for(;;);
    return 0;
}