记录编号	393445	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2009] 狼和羊的故事	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.114 s
提交时间	2017-04-11 11:21:53	内存使用	0.55 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 100*100+100;
int dist[MAXN];
bool vis[MAXN];
int s, t;
int n, m;
struct edge{
  int to, rem;
}; vector<edge> es;
vector<int> G[MAXN];
void addedge(int u, int v, int f){
  es.push_back((edge){v, f});
  es.push_back((edge){u, 0});
  int k = es.size();
  G[u].push_back(k-2); G[v].push_back(k-1);
}
int getp(int x, int y){
  return m*(x-1)+y;
}
bool bfs(){
  memset(vis, false, sizeof vis);
  queue<int> q;
  dist[s] = 0;
  q.push(s); vis[s] = true;
  while(!q.empty()){
    int u = q.front(); q.pop();
    for(int i = 0; i < G[u].size(); i++){
      edge &e = es[G[u][i]];
      if(e.rem > 0 && !vis[e.to]){
        q.push(e.to); dist[e.to] = dist[u]+1; vis[e.to] = true;
      }
    }
  }
  return vis[t];
}
int cure[MAXN];
int dfs(int u, int f){
  if(u == t || !f)return f;
  int tot = 0;
  for(int &i = cure[u]; i < G[u].size(); i++){
    edge &e = es[G[u][i]];
    int next = 0;
    if(dist[e.to] == dist[u]+1 && (next = dfs(e.to, min(f, e.rem))) > 0){
      e.rem -= next, tot += next, es[G[u][i]^1].rem += next, f -= next;
      if(!f)break;
    }
  }
  return tot;
}
int maxflow(){
  int f = 0;
  while(bfs()){
    memset(cure, 0, sizeof cure);
    f += dfs(s, 0x7fffffff);
  }
  return f;
}
int a[102][102];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int main(){
  freopen("ws.in", "r", stdin);
  freopen("ws.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]);
  s = 0, t = getp(n,m)+1;
  for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++){
    if(a[i][j] == 1)addedge(s, getp(i, j), 0x7fffffff);
    else if(a[i][j] == 2){
      addedge(getp(i, j), t, 0x7fffffff);
      continue;
    }
    for(int k = 0; k < 4; k++){
      int nx = i+dx[k], ny = j+dy[k];
      if(nx > 0 && nx <= n && ny > 0 && ny <= m)
        addedge(getp(i, j), getp(nx, ny), 1);
    }
  }
  printf("%d\n", maxflow());
  return 0;
}