hdu 2732（网络流）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2732

思路：如果从某一根柱子能够直接跳到迷宫的外面，那么我们就将这个点连接到汇点。对于哪些不能跳出去但是又有柱子的点，那么我们就去按照跳跃距离搜寻有没有其他的柱子能够去跳跃，如果能够找到的话，那么连接这两点，并且将容量控制为弧尾节点的柱子数，也正是由于一条弧只能够约束一个顶点，所以我们需要进行拆点，点内之间流量为本身柱子数。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 #define MAXN 2222
  7 #define MAXM 2222222
  8 #define inf 1<<30
  9 struct Edge{
 10    int v,cap,next;
 11 }edge[MAXM];
 12 int head[MAXN];
 13 int pre[MAXN];
 14 int cur[MAXN];
 15 int level[MAXN];
 16 int gap[MAXN];
 17 int n,m,d,vs,vt,NE,NV;
 18 
 19 void Insert(int u,int v,int cap,int cc=0){
 20    edge[NE].v=v;edge[NE].cap=cap;
 21    edge[NE].next=head[u];head[u]=NE++;
 22 
 23    edge[NE].v=u;edge[NE].cap=cc;
 24    edge[NE].next=head[v];head[v]=NE++;
 25 }
 26 
 27 int sap(int vs,int vt){
 28    memset(pre,-1,sizeof(pre));
 29    memset(level,0,sizeof(level));
 30    memset(gap,0,sizeof(gap));
 31    memcpy(cur,head,sizeof(head));
 32    int u=pre[vs]=vs,aug=inf,maxflow=0;
 33    gap[0]=NV;
 34    while(level[vs]<NV){
 35       loop:
 36       for(int &i=cur[u];i!=-1;i=edge[i].next){
 37          int v=edge[i].v;
 38          if(edge[i].cap&&level[u]==level[v]+1){
 39             aug=min(aug,edge[i].cap);
 40             pre[v]=u;
 41             u=v;
 42             if(v==vt){
 43                maxflow+=aug;
 44                for(u=pre[v];v!=vs;v=u,u=pre[u]){
 45                   edge[cur[u]].cap-=aug;
 46                   edge[cur[u]^1].cap+=aug;
 47                }
 48                aug=inf;
 49             }
 50             goto loop;
 51          }
 52       }
 53       int minlevel=NV;
 54       for(int i=head[u];i!=-1;i=edge[i].next){
 55          int v=edge[i].v;
 56          if(edge[i].cap&&level[v]<minlevel){
 57             minlevel=level[v];
 58             cur[u]=i;
 59          }
 60       }
 61       if(--gap[level[u]]==0)break;
 62       level[u]=minlevel+1;
 63       gap[level[u]]++;
 64       u=pre[u];
 65    }
 66    return maxflow;
 67 }
 68 
 69 char G1[22][22];
 70 char G2[22][22];
 71 int map[22][22];
 72 int mat[22][22];
 73 
 74 int main(){
 75  //  freopen("1.txt","r",stdin);
 76    int _case,t=1,total,sum;
 77    scanf("%d",&_case);
 78    while(_case--){
 79       scanf("%d%d",&n,&d);
 80       memset(map,0,sizeof(map));
 81       memset(mat,0,sizeof(mat));
 82       memset(head,-1,sizeof(head));
 83       for(int i=0;i<n;i++)scanf("%s",G1[i]);
 84       for(int i=0;i<n;i++)scanf("%s",G2[i]);
 85       m=strlen(G1[0]),NE=0,vs=0,total=0,sum=0;
 86       for(int i=0;i<n;i++){
 87          for(int j=0;j<m;j++){
 88             map[i][j]=G1[i][j]-'0';
 89             if(map[i][j]){ mat[i][j]=++total;Insert(2*total-1,2*total,map[i][j]); }
 90          }
 91       }
 92       vt=2*total+1,NV=vt+1;
 93       for(int i=0;i<n;i++){
 94          for(int j=0;j<m;j++){
 95             if(G2[i][j]=='L'){ sum++;Insert(vs,2*mat[i][j]-1,1); }
 96          }
 97       }
 98       for(int i=0;i<n;i++){
 99          for(int j=0;j<m;j++)if(mat[i][j]){
100             for(int x=-d;x<=d;x++){
101                for(int y=abs(x)-d;y<=d-abs(x);y++){
102                   int ii=i+x,jj=j+y;
103                   if(ii<0||ii>=n||jj<0||jj>=m)continue;
104                   else if(ii==i&&jj==j)continue;
105                   else if(mat[ii][jj]==0)continue;
106                   Insert(2*mat[i][j],2*mat[ii][jj]-1,inf);
107                }
108             }
109             if(i<d||j<d||n-i<=d||m-j<=d)Insert(2*mat[i][j],vt,inf);
110          }
111       }
112       int ans=sum-sap(vs,vt);
113       printf("Case #%d: ",t++);
114       if(ans==0){
115          printf("no lizard was left behind.\n");
116       }else if(ans==1){
117          printf("1 lizard was left behind.\n");
118       }else {
119          printf("%d lizards were left behind.\n",ans);
120       }
121    }
122    return 0;
123 }

View Code