hdu 2732 最大流 **

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

链接：点我

看懂了，明天拍

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<queue>
  7 #include<map>
  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("*****
");
 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_JUDGE
104     freopen("1.in","r",stdin);
105     #endif
106     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<n;i++)
115         {
116             scanf("%s",&s1[i]);
117         }
118         m=strlen(s1[0]);
119         int tot=0;
120         cl(maze);
121         for(i=0;i<n;i++)
122         {
123             for(j=0;j<m;j++)
124             {
125                 if(s1[i][j]>'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;i++)
135         {
136             scanf("%s",s2[i]);
137             for(j=0;j<m;j++)
138             {
139                 if(s2[i][j]=='L')
140                 {
141                     sum++;
142                     addedge(start,2*maze[i][j]-1,1);
143                 }
144             }
145         }
146         for(i=0;i<n;i++)
147         {
148             for(j=0;j<m;j++)
149             {
150                 if(maze[i][j])      //能直接跳出边界的点连上汇点
151                 {
152                     for(int x=-d;x<=d;x++)
153                     {
154                         for(int y=fabs(x)-d;y<=d-fabs(x);y++)   //新技能get
155                         {
156                             int ni=i+x;
157                             int nj=j+y;
158                             if(ni<0||ni>=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||j<d||n-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.
",ca);
170         else if(ans==1)printf("Case #%d: 1 lizard was left behind.
",ca);
171         else printf("Case #%d: %d lizards were left behind.
",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 <iostream>
 10 #include <string.h>
 11 #include <stdio.h>
 12 #include <algorithm>
 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]<nodenum)
 44     {
 45         loop:
 46         for(int &i=cur[u];i!=-1;i=edge[i].next)
 47         {
 48             int v=edge[i].to;
 49             if(edge[i].cap&&dis[u]==dis[v]+1)
 50             {
 51                 if(aug==-1||aug>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<n;i++)
104             scanf("%s",&g1[i]);
105         int m=strlen(g1[0]);
106         memset(mat,0,sizeof(mat));
107         for(int i=0;i<n;i++)
108             for(int j=0;j<m;j++)
109                 if(g1[i][j]>'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;i++)
119         {
120             scanf("%s",&g2[i]);
121             for(int j=0;j<m;j++)
122                 if(g2[i][j]=='L')
123                 {
124                     sum++;
125                     addedge(start,2*mat[i][j]-1,1);
126                 }
127         }
128         for(int i=0;i<n;i++)
129             for(int j=0;j<m;j++)
130                 if(mat[i][j])
131                 {
132                     for(int x=-d;x<=d;x++)
133                         for(int y=abs(x)-d;y<=d-abs(x);y++)
134                         {
135                             int newi=i+x;
136                             int newj=j+y;
137                             if(newi<0||newi>=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||j<d||n-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.
",iCase);
147         else if(ans==1)printf("Case #%d: 1 lizard was left behind.
",iCase);
148         else printf("Case #%d: %d lizards were left behind.
",iCase,ans);
149     }
150     return 0;
151 }
2015/5/26
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/cnblogs321114287/p/4531446.html