ZJOI2009 狼和羊的故事

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define inf 0x7fffffff
 5 #define T 10001
 6 using namespace std;
 7 int head[10005],q[10005],h[10005];
 8 int cnt=1,ans,n,m;
 9 int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0},mp[105][105];
10 struct data{int to,next,v;}e[500001];
11 void ins(int u,int v,int w)
12 {e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;}
13 void insert(int u,int v,int w)
14 {ins(u,v,w);ins(v,u,0);}
15 bool bfs()
16 {
17      int t=0,w=1,i,now;
18      memset(h,-1,sizeof(h));
19      q[0]=0;h[0]=0;
20      while(t<w)
21      {
22                now=q[t];t++;i=head[now];
23                while(i)
24                {
25                        if(e[i].v&&h[e[i].to]==-1)
26                        {
27                                                  h[e[i].to]=h[now]+1;
28                                                  q[w++]=e[i].to;
29                                                  }
30                        i=e[i].next;
31                        }
32                }
33     return h[T]==-1? 0:1;
34  }
35 int dfs(int x,int f)
36 {
37     if(x==T)return f;
38     int w,used=0,i;
39     i=head[x];
40     while(i)
41     {
42             if(e[i].v&&h[e[i].to]==h[x]+1)
43             {
44                                           w=f-used;
45                                           w=dfs(e[i].to,min(w,e[i].v));
46                                           e[i].v-=w;
47                                           e[i^1].v+=w;
48                                           used+=w;
49                                           if(used==f)return f;
50                                           }
51             i=e[i].next;
52             }
53     if(!used)h[x]=-1;
54     return used;
55 }
56 void dinic(){while(bfs())ans+=dfs(0,inf);}
57 void ini()
58 {
59      scanf("%d%d",&n,&m);
60      for(int i=1;i<=n;i++)
61          for(int j=1;j<=m;j++)
62              scanf("%d",&mp[i][j]);
63      }
64 void build()
65 {
66      for(int i=1;i<=n;i++)
67          for(int j=1;j<=m;j++)
68          {
69              if(mp[i][j]==1)insert(0,(i-1)*m+j,inf);
70              else if(mp[i][j]==2)insert((i-1)*m+j,T,inf);
71              for(int k=0;k<4;k++)
72              {
73                      int nowx=i+xx[k],nowy=j+yy[k];
74                      if(nowx<1||nowx>n||nowy<1||nowy>m||mp[i][j]==2)continue;
75                      if(mp[i][j]!=1||mp[nowx][nowy]!=1)
76                      insert((i-1)*m+j,(nowx-1)*m+nowy,1);
77                      }
78              }
79      }
80 int main()
81 {
82     ini();
83     build();
84     dinic();
85     printf("%d",ans);
86     return 0;
87     }