bzoj1412

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <queue>
 5 #define INF 0xfffffff
 6 #define g(b) g[b.x][b.y]
 7 #define h(b) h[b.x][b.y]
 8 #define maxn 110
 9 #define inc(i,j,k) for(int i=j;i<=k;i++)
10 using namespace std;
11 
12 //edge
13 struct p{int x,y;}; struct e{p t;int c,n;}; e es[200000*2]; int ess,g[maxn][maxn];
14 void pe(p f,p t,int c){
15     es[++ess]=(e){t,c,g(f)}; g(f)=ess; 
16     es[++ess]=(e){f,0,g(t)}; g(t)=ess; 
17 }
18 
19 //maxflow
20 queue <p> q; int h[maxn][maxn];
21 bool bfs(p s,p t){//构建层次图 
22     while(! q.empty())q.pop(); memset(h,-1,sizeof(h)); h(s)=0; q.push(s);
23     while(! q.empty()){
24         p now=q.front(); q.pop();
25         for(int i=g(now);i!=-1;i=es[i].n)if(h(es[i].t)==-1&&es[i].c>0){
26             h(es[i].t)=h(now)+1; q.push(es[i].t);
27         }
28     }
29     return (h(t)==-1)?0:1;
30 }
31 int dfs(p x,p t,int flow){//找增广路并增广 
32     if(x.x==t.x&&x.y==t.y)return flow;
33     int used=0;
34     for(int i=g(x);i!=-1;i=es[i].n)if(es[i].c>0&&h(es[i].t)==h(x)+1){
35         int w=dfs(es[i].t,t,min(flow,es[i].c));
36         es[i].c-=w; es[i^1].c+=w; used+=w; flow-=w; if(flow==0)return used;
37     }
38     if(! used)h(x)=-1; return used;
39 }
40 int dicnic(p s,p t){int flow=0; while(bfs(s,t))flow+=dfs(s,t,INF); return flow;}
41 
42 //main
43 int n,m,graph[maxn][maxn];
44 int main(){
45     //freopen("zs.txt","r",stdin);
46     scanf("%d%d",&n,&m);
47     inc(i,1,n)inc(j,1,m)scanf("%d",&graph[i][j]);
48     memset(g,-1,sizeof(g)); ess=-1;
49     inc(i,1,n)inc(j,1,m){
50         if(graph[i][j]==2)pe((p){0,0},(p){i,j},INF);
51         if(graph[i][j]==1)pe((p){i,j},(p){n+1,m+1},INF);
52         if(i-1>0)pe((p){i,j},(p){i-1,j},1);
53         if(i+1<=n)pe((p){i,j},(p){i+1,j},1);
54         if(j-1>0)pe((p){i,j},(p){i,j-1},1);
55         if(j+1<=m)pe((p){i,j},(p){i,j+1},1);
56     }
57     printf("%d",dicnic((p){0,0},(p){n+1,m+1}));    
58     return 0;
59 }