记录编号	389286	评测结果	AAAAAAAAAAA
题目名称	[网络流24题] 方格取数问题	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2017-03-31 06:57:45	内存使用	0.33 MiB

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 1000+10;
struct edge{
  int from, to, rem;
}; vector<edge> edges;
vector<int> G[MAXN];
void addedge(int u, int v, int f){
  edges.push_back((edge){u, v, f});
  edges.push_back((edge){v, u, 0});
  int k = edges.size();
  G[u].push_back(k-2); G[v].push_back(k-1);
}
int dist[MAXN]; bool vis[MAXN];
int s, t;
bool bfs(){
  dist[s] = 0;
  memset(vis, false, sizeof(vis));
  vis[s] = true;
  queue<int> q;
  q.push(s);
  while(!q.empty()){
    int u = q.front(); q.pop();
    for(int i = 0; i < G[u].size(); i++){
      edge &e = edges[G[u][i]];
      if(e.rem > 0 && !vis[e.to]){
        vis[e.to] = true;
        dist[e.to] = dist[u]+1;
        q.push(e.to);
      }
    }
  }
  return vis[t];
}
int dfs(int u, int f){
  if(u == t || !f)return f;
  int tot = 0;
  for(int i = 0; i < G[u].size(); i++){
    edge &e = edges[G[u][i]]; int next;
    if(dist[e.to] == dist[u]+1 && (next = dfs(e.to, min(f, e.rem))) > 0){
      f -= next, tot += next, e.rem -= next, edges[1^G[u][i]].rem += next;
      if(!f)break;
    }
  }
  return tot;
}
int maxf(){
  int f = 0;
  while(bfs())
    f += dfs(s, 0x7fffffff);
  return f;
}
int m, n;
inline int getv(int x, int y){
  return (x-1)*n+y;
}
int main(){
 // freopen("test_data.txt", "r", stdin);
  freopen("grid.in", "r", stdin); freopen("grid.out", "w", stdout);
  scanf("%d %d", &m, &n);
  s = n*m+1, t = s+1;
  int tot = 0;
  for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++){
    int v; scanf("%d", &v);
    tot += v;
    if((i+j)&1)addedge(s, getv(i, j), v); //black
    else addedge(getv(i, j), t, v); //white
    if((i+j)&1){ //black
      for(int dx = -1; dx <= 1; dx++)for(int dy = -1; dy <= 1; dy++){
        if(dx + dy && dx*dy == 0 && i+dx <= m && i+dx >= 1 && j+dy <= n && j+dy >= 1)
          addedge(getv(i, j), getv(i+dx, j+dy), 0x7fffffff);
      }
    }
  }
  tot -= maxf();
  printf("%d\n", tot);
  return 0;
}