记录编号	480283	评测结果	AAAAAAAAAAA
题目名称	[网络流24题] 方格取数问题	最终得分	100
用户昵称	nonamenotitle	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2017-12-25 23:02:38	内存使用	0.34 MiB

#include <bits/stdc++.h>
using namespace std;
const int maxn=35;
const int inf=0x3f3f3f3f;
int a[maxn][maxn];
int n,m,S,T,tot=0;
struct edge{
    int to,cap,rev;
    edge(int to=0,int cap=0,int rev=0): to(to),cap(cap),rev(rev) {}
};
vector<edge > g[maxn*maxn+5];
inline int id(int x,int y){return (x-1)*m+y;}
void addedge(int u,int v,int cap)
{
    g[u].push_back(edge(v,cap,g[v].size()));
    g[v].push_back(edge(u,0,(int)g[u].size()-1));
}
int dis[maxn*maxn+5],q[maxn*maxn+5],N,cur[maxn*maxn+5];
bool bfs(int st,int ed)
{
    memset(dis,-1,sizeof(dis));
    dis[st]=0;
    int head=0,tail=0;
    q[head]=st;
    while(head<=tail) {
        int v=q[head%N];head++;
        for(int i=0;i<(int)g[v].size();i++) {
            edge& e=g[v][i];
            if(e.cap>0 && dis[e.to]==-1) {
                dis[e.to]=dis[v]+1;
                tail++;q[tail%N]=e.to;
            }
        }
    }
    return (~dis[ed]);
}
int dfs(int v,int ed,int F)
{
    if(v==ed) return F;
    for(int &i=cur[v];i<(int)g[v].size();i++) {
        edge& e=g[v][i];
        if(e.cap>0 && dis[e.to]==dis[v]+1) {
            int d=dfs(e.to,ed,min(F,e.cap));
            if(d>0) {
                e.cap-=d;
                g[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
int MaxF(int st,int ed)
{
    int ret=0,tmp=0;
    while(bfs(st,ed)) {
        memset(cur,0,sizeof(cur));
        while((tmp=dfs(st,ed,inf))>0) ret+=tmp;
    }
    return ret;
}
int main()
{
    freopen("grid.in","r",stdin);
    freopen("grid.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {scanf("%d",&a[i][j]);tot+=a[i][j];}
    }
    S=0,T=n*m+1;
    for(int i=1;i<=n;i++) {
        for(int j=1+(i%2==0);j<=m;j+=2) {
            if(j+1<=m) addedge(id(i,j),id(i,j+1),inf);
            if(j-1>=1) addedge(id(i,j),id(i,j-1),inf);
        }
    }
    for(int i=1;i<=m;i++) {
        for(int j=1+(i%2==0);j<=n;j+=2) {
            if(j+1<=n) addedge(id(j,i),id(j+1,i),inf);
            if(j-1>=1) addedge(id(j,i),id(j-1,i),inf);
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if((i&1)==(j&1)) addedge(S,id(i,j),a[i][j]);
            else addedge(id(i,j),T,a[i][j]);
        }
    }
    N=n*m+5;
    printf("%d\n",tot-MaxF(S,T));
    return 0;
}