hdu 2732 最大流 **-白红宇

hdu 2732 最大流 **

阅读量：5377 次

发布时间：2019-06-15

本文共 6694 字，大约阅读时间需要 22 分钟。

题意：题目是说一个n*m的迷宫中，有每个格子有柱子。柱子高度为0~3，高度为0的柱子是不能站的（高度为0就是没有柱子）在一些有柱子的格子上有一些蜥蜴，一次最多跳距离d,相邻格子的距离是1，只要跳出迷宫就是安全的。这个距离是曼哈顿距离（好像是的）。蜥蜴一次最多跳距离d,但是起跳的地方的柱子高度会减一，一个柱子同一时间只能有一个蜥蜴要求最少几个不能逃出迷宫。

链接：

看懂了，明天拍

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
            8 using namespace std; 9 #define MOD 1000000007 10 #define pb(a) push_back(a) 11 const int INF=0x3f3f3f3f; 12 const double eps=1e-5; 13 typedef long long ll; 14 #define cl(a) memset(a,0,sizeof(a)) 15 #define ts printf("*****\n"); 16 const int MAXN=2200; 17 int n,m,tt,cnt; 18 char s1[30][30],s2[30][30]; 19 struct Edge 20 { 21 int to,next,cap,flow; 22 }edge[200020];//注意是MAXM 23 int tol; 24 int head[MAXN]; 25 int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN]; 26 int maze[30][30]; 27 void init() 28 { 29 tol = 0; 30 memset(head,-1,sizeof(head)); 31 } 32 //加边，单向图三个参数，双向图四个参数 33 void addedge(int u,int v,int w,int rw=0) 34 { 35 edge[tol].to = v;edge[tol].cap = w;edge[tol].next = head[u]; 36 edge[tol].flow = 0;head[u] = tol++; 37 edge[tol].to = u;edge[tol].cap = rw;edge[tol].next = head[v]; 38 edge[tol].flow = 0;head[v]=tol++; 39 } 40 //输入参数：起点、终点、点的总数 41 //点的编号没有影响，只要输入点的总数 42 int sap(int start,int end,int N) 43 { 44 memset(gap,0,sizeof(gap)); 45 memset(dep,0,sizeof(dep)); 46 memcpy(cur,head,sizeof(head)); 47 int u = start; 48 pre[u] = -1; 49 gap[0] = N; 50 int ans = 0; 51 while(dep[start] < N) 52 { 53 if(u == end) 54 { 55 int Min = INF; 56 for(int i = pre[u];i != -1; i = pre[edge[i^1].to]) 57 if(Min > edge[i].cap - edge[i].flow) 58 Min = edge[i].cap - edge[i].flow; 59 for(int i = pre[u];i != -1; i = pre[edge[i^1].to]) 60 { 61 edge[i].flow += Min; 62 edge[i^1].flow -= Min; 63 } 64 u = start; 65 ans += Min; 66 continue; 67 } 68 bool flag = false; 69 int v; 70 for(int i = cur[u]; i != -1;i = edge[i].next) 71 { 72 v = edge[i].to; 73 if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]) 74 { 75 flag = true; 76 cur[u] = pre[v] = i; 77 break; 78 } 79 } 80 if(flag) 81 { 82 u = v; 83 continue; 84 } 85 int Min = N; 86 for(int i = head[u]; i != -1;i = edge[i].next) 87 if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min) 88 { 89 Min = dep[edge[i].to]; 90 cur[u] = i; 91 } 92 gap[dep[u]]--; 93 if(!gap[dep[u]])return ans; 94 dep[u] = Min+1; 95 gap[dep[u]]++; 96 if(u != start) u = edge[pre[u]^1].to; 97 } 98 return ans; 99 }100 int main()101 {102 int i,j,k;103 #ifndef ONLINE_JUDGE104 freopen("1.in","r",stdin);105 #endif106 scanf("%d",&tt);107 int ca=0;108 int d;109 while(tt--)110 {111 ca++;112 init();113 scanf("%d%d",&n,&d);114 for(i=0;i
            
             '0') //说明改点可跳126 {127 maze[i][j]=++tot;128 addedge(2*tot-1,2*tot,s1[i][j]-'0');129 }130 }131 } //这里的tot要注意，如果一开始是tot++，那么比实际会多出一个点132 int start=0,end=2*tot+1,nodenum=2*tot+2;133 int sum=0;134 for(i=0;i
             
              =n||nj<0||nj>=m)continue;159 if(ni==i&&nj==j) continue;160 if(maze[ni][nj]==0) continue;161 addedge(2*maze[i][j],2*maze[ni][nj]-1,INF); //这里的跳跃是无限流的162 }163 }164 if(i
              
               
                <=d||m-j<=d) addedge(2*maze[i][j],end,INF);165 }166 }167 }168 int ans=sum-sap(start,end,nodenum);169 if(ans==0)printf("Case #%d: no lizard was left behind.\n",ca);170 else if(ans==1)printf("Case #%d: 1 lizard was left behind.\n",ca);171 else printf("Case #%d: %d lizards were left behind.\n",ca,ans);172 }173 }

1 //============================================================================  2 // Name        : HDU.cpp  3 // Author      :   4 // Version     :  5 // Copyright   : Your copyright notice  6 // Description : Hello World in C++, Ansi-style  7 //============================================================================  8   9 #include 
      
        10 #include 
       
         11 #include 
        
          12 #include 
         
           13 using namespace std; 14  15 const int MAXN=2200; 16 const int MAXM=200020; 17 const int INF=0x3f3f3f3f; 18 struct Node 19 { 20     int to,next,cap; 21 }edge[MAXM];//注意是MAXM 22 int tol; 23 int head[MAXN]; 24 int gap[MAXN],dis[MAXN],pre[MAXN],cur[MAXN]; 25  26 void init() 27 { 28     tol=0; 29     memset(head,-1,sizeof(head)); 30 } 31 void addedge(int u,int v,int w,int rw=0) 32 { 33     edge[tol].to=v;edge[tol].cap=w;edge[tol].next=head[u];head[u]=tol++; 34     edge[tol].to=u;edge[tol].cap=rw;edge[tol].next=head[v];head[v]=tol++; 35 } 36 int sap(int start,int end,int nodenum) 37 { 38     memset(dis,0,sizeof(dis)); 39     memset(gap,0,sizeof(gap)); 40     memcpy(cur,head,sizeof(head)); 41     int u=pre[start]=start,maxflow=0,aug=-1; 42     gap[0]=nodenum; 43     while(dis[start]
          
           edge[i].cap) 52                     aug=edge[i].cap; 53                 pre[v]=u; 54                 u=v; 55                 if(v==end) 56                 { 57                     maxflow+=aug; 58                     for(u=pre[u];v!=start;v=u,u=pre[u]) 59                     { 60                         edge[cur[u]].cap-=aug; 61                         edge[cur[u]^1].cap+=aug; 62                     } 63                     aug=-1; 64                 } 65                 goto loop; 66             } 67         } 68         int mindis=nodenum; 69         for(int i=head[u];i!=-1;i=edge[i].next) 70         { 71             int v=edge[i].to; 72             if(edge[i].cap&&mindis>dis[v]) 73             { 74                 cur[u]=i; 75                 mindis=dis[v]; 76             } 77         } 78         if((--gap[dis[u]])==0)break; 79         gap[dis[u]=mindis+1]++; 80         u=pre[u]; 81     } 82     return maxflow; 83 } 84  85 char g1[30][30]; 86 char g2[30][30]; 87 int mat[30][30]; 88  89 int main() 90 { 91     //freopen("in.txt","r",stdin); 92     //freopen("out.txt","w",stdout); 93     int T; 94     int n,d; 95     int iCase=0; 96     scanf("%d",&T); 97     while(T--) 98     { 99         iCase++;100         scanf("%d%d",&n,&d);101         init();102         int tol=0;103         for(int i=0;i
           
            '0')110 {111 mat[i][j]=++tol;112 addedge(2*tol-1,2*tol,g1[i][j]-'0');113 }114 115 int start=0,end=2*tol+1,nodenum=2*tol+2;116 //进行拆点，加上源点和汇点，共2*tol+2个点。117 int sum=0;//总数118 for(int i=0;i
            
             =n||newj<0||newj>=m)continue;138 if(mat[newi][newj]==0)continue;139 if(newi==i&&newj==j)continue;140 addedge(2*mat[i][j],2*mat[newi][newj]-1,INF);141 }142 if(i
             
              
               <=d||m-j<=d)143 addedge(2*mat[i][j],end,INF);144 }145 int ans=sum-sap(start,end,nodenum);146 if(ans==0)printf("Case #%d: no lizard was left behind.\n",iCase);147 else if(ans==1)printf("Case #%d: 1 lizard was left behind.\n",iCase);148 else printf("Case #%d: %d lizards were left behind.\n",iCase,ans);149 }150 return 0;151 }

2015/5/26

转载于:https://www.cnblogs.com/cnblogs321114287/p/4531446.html

你可能感兴趣的文章