首页 / C++ / C++之路进阶——最大流（紧急疏散）
C++之路进阶——最大流（紧急疏散）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C++之路进阶——最大流（紧急疏散），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7264字，纯文字阅读大概需要11分钟。
内容图文
3566 紧急疏散
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
发生了火警，所有人员需要紧急疏散！假设每个房间是一个N M的矩形区域。每个格子如果是‘.‘，那么表示这是一块空地；如果是‘X‘，那么表示这是一面墙，如果是‘D‘，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。最初，每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地上就没有人数限制了（也就是说每块空地可以同时站无数个人）。但是，由于门很窄，每一秒钟只能有一个人移动到门的位置，一旦移动到门的位置，就表示他已经安全撤离了。现在的问题是：如果希望所有的人安全撤离，最短需要多少时间？或者告知根本不可能。
输入描述 Input Description
输入文件第一行是由空格隔开的一对正整数N与M，3<=N <=20，3<=M<=20，以下N行M列描述一个N M的矩阵。其中的元素可为字符‘.‘、‘X‘和‘D‘，且字符间无空格。
输出描述 Output Description
只有一个整数K，表示让所有人安全撤离的最短时间，如果不可能撤离，那么输出‘impossible‘（不包括引号）.
样例输入 Sample Input
5 5
XXXXX
X...D
XX.XX
X..XX
XXDXX
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
3<=N <=20，3<=M<=20
题解：
对于每个门进行一次bfs，得出每个点到每个门的时间
然后二分时间，每次建图dinic
S到空地连一条容量1的边，
每个空地到可到达的门连一条容量1的边，
每个门到T连一条容量为时间的边
代码：
（对于codevs来说）：
1 #include<queue>
2 #include<cstdio>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6#define INF 0x7fffffff
7#define maxn 1001
8#define S 0
9#define T 1000
10 11usingnamespace std;
12 13int n,m,head[maxn],dis[401][21][21],ans,tot,cnt=1,door=1,layered[maxn],map[21][21],finallyans=-1;
14int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
15 16struct ss
17 {
18int x;
19int y;
20int s;
21 ss() {};
22 ss(int a,int b,int c)
23 {
24 x=a;
25 y=b;
26 s=c;
27 };
28 };
29 30struct node
31 {
32int to;
33int next;
34int edge;
35 }e[1000001];
36 37void add(int u,int v,int c)
38 {
39 e[++cnt].to=v;
40 e[cnt].next=head[u];
41 e[cnt].edge=c;
42 head[u]=cnt;
43 }
44 45void insert(int u,int v,int c)
46 {
47 add(u,v,c);
48 add(v,u,0);
49 }
50 51bool bfs()
52 {
53for (int i=1;i<=T;i++) layered[i]=INF;
54 queue<int>que;
55 que.push(S);
56while (!que.empty())
57 {
58int now=que.front();
59 que.pop();
60for (int i=head[now];i;i=e[i].next)
61if (e[i].edge&&layered[e[i].to]>layered[now]+1)
62 {
63 layered[e[i].to]=layered[now]+1;
64 que.push(e[i].to);
65if (e[i].to==T) return1;
66 }
67 }
68return0;
69 }
70 71int dfs(int x,int inf)
72 {
73if (x==T) return inf;
74int rest=inf;
75for (int i=head[x];i&&rest;i=e[i].next)
76if (e[i].edge&&layered[e[i].to]==layered[x]+1)
77 {
78int now=dfs(e[i].to,min(rest,e[i].edge));
79if (!layered[now]) layered[now]=0;
80 e[i].edge-=now;
81 e[i^1].edge+=now;
82 rest-=now;
83 }
84return inf-rest;
85 }
86 87int dinic()
88 {
89int ansn=0;
90while (bfs()) ansn+=dfs(S,INF);
91return ansn;
92 }
93 94void built(int x)
95 {
96 memset(head,0,sizeof (head));
97 cnt=1;
98for (int i=1;i<=n;i++)
99for (int j=1;j<=m;j++)
100if (map[i][j]==1)
101 {
102int v=(i-1)*m+j;
103 insert(S,v,1);
104 }
105for (int i=2;i<=door;i++) insert(n*m+i,T,x);
106for (int i=2;i<=door;i++)
107for (int j=1;j<=n;j++)
108for (int k=1;k<=m;k++)
109if (dis[i][j][k]<=x) insert((j-1)*m+k,n*m+i,x);
110 }
111112bool judge(int x)
113 {
114 built(x);
115int ans=dinic();
116if (ans==tot) return1;
117elsereturn0;
118 }
119120void search(int k,int x,int y)
121 {
122 queue<ss>que;
123 que.push(ss(x,y,0));
124while (!que.empty())
125 {
126for (int i=0;i<4;i++)
127 {
128int nowx=que.front().x+xx[i];
129int nowy=que.front().y+yy[i];
130int s=que.front().s;
131if(nowx<1||nowy<1||nowx>n||nowy>m||map[nowx][nowy]!=1) continue;
132if (dis[k][nowx][nowy]==INF)
133 {
134 dis[k][nowx][nowy]=s+1;
135 que.push(ss(nowx,nowy,s+1));
136 }
137 }
138 que.pop();
139 }
140 }
141int main()
142 {
143char ch[100];
144 scanf("%d%d",&n,&m);
145for (int i=1;i<=n;i++)
146 {
147 scanf("%s",ch);
148for (int j=1;j<=m;j++)
149 {
150if (ch[j-1]==‘.‘) map[i][j]=1,tot++;
151if (ch[j-1]==‘D‘) map[i][j]=++door;
152 }
153 }
154for (int i=2;i<=door;i++)
155for (int j=1;j<=n;j++)
156for (int k=1;k<=m;k++)
157 dis[i][j][k]=INF;
158for (int i=1;i<=n;i++)
159for (int j=1;j<=m;j++)
160if (map[i][j]>1) search(map[i][j],i,j);
161int l=0,r=400;
162while (l<=r)
163 {
164int mid=(l+r)>>1;
165if (judge(mid)) finallyans=r=mid,r--;
166else l=mid+1;
167 }
168if (finallyans==-1) printf("impossible");
169else printf("%d",finallyans);
170return0;
171 }
对于bzoj来说：
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4usingnamespace std;
5#define mid (l+r)/2
6#define inf 0x7fffffff
7#define T n*n*m*m+2
8constint N=30;
9constint M=200000;
10char s[N];
11bool use[N][N],flag[N][N];
12struct S{int x,y,c;}l[N*N];
13struct Q{int st,en,va;}aa[M*2];
14int n,m,map[N][N],f[N][N][N][N],sum,point[M],next[M*2],cur[M],dis[M],pre[M],gap[M],tot;
15int xi[4]={-1,0,0,1},yi[4]={0,-1,1,0};
16 inline void bfs(int xa,int ya){
17int i,h,t,k,x,y;
18 memset(use,1,sizeof(use));
19 h=t=1;l[h].x=xa;l[h].y=ya;l[h].c=0;
20while(h<=t){
21 x=l[h].x;y=l[h].y;
22for(i=0;i<4;++i){
23int xx=x+xi[i],yy=y+yi[i];
24if(xx>0&&xx<=n&&yy>0&&y<=m&&map[xx][yy]==1&&use[xx][yy]){
25 l[++t].x=xx;l[t].y=yy;l[t].c=l[h].c+1;
26 use[xx][yy]=false;
27 f[xx][yy][xa][ya]=l[t].c;
28 flag[xx][yy]=true;
29 }
30 }
31 h+=1;
32 }
33}
34 inline void add(int x,int y,int z){
35 tot+=1;next[tot]=point[x];point[x]=tot;
36 aa[tot].st=x;aa[tot].en=y;aa[tot].va=z;
37 tot+=1;next[tot]=point[y];point[y]=tot;
38 aa[tot].st=y;aa[tot].en=x;aa[tot].va=0;
39}
40 inline int ISAP(int ss,int tt){
41bool f;
42int minn,ans=0,i,u,y;
43 memset(dis,0,sizeof(dis));
44 memset(gap,0,sizeof(gap));
45 memset(pre,0,sizeof(pre));
46 gap[0]=tt-ss+1; u=ss;
47for(i=ss;i<=tt;++i) cur[i]=point[i];
48while(dis[ss]<tt-ss+1){
49 f=false;
50for(i=cur[u];i;i=next[i])
51if(aa[i].va>0&&dis[u]==dis[aa[i].en]+1){
52 cur[u]=i;f=true;break;
53 }
54if(f){
55 pre[u=aa[i].en]=i;
56if(u==tt){
57 minn=inf;
58for(i=u;i!=ss;i=aa[pre[i]].st)
59 minn=min(minn,aa[pre[i]].va);
60 ans+=minn;
61for(i=u;i!=ss;i=aa[pre[i]].st){
62 aa[pre[i]].va-=minn;
63 aa[pre[i]^1].va+=minn;
64 }
65 u=ss;
66 }
67 }
68else{
69 --gap[dis[u]];
70if(!gap[dis[u]]) return ans;
71 y=2*tt; cur[u]=point[u];
72for(i=point[u];i;i=next[i])
73if(aa[i].va>0) y=min(y,dis[aa[i].st]);
74 ++gap[dis[u]=y+1];
75if(u!=ss) u=aa[pre[u]].st;
76 }
77 }
78return ans;
79}
80 inline bool check(int x){
81int i,j,p,q;
82 tot=1;
83 memset(point,0,sizeof(point));
84 memset(next,0,sizeof(next));
85for(i=1;i<=n;++i)
86for(j=1;j<=m;++j){
87int now=((i-1)*m+j-1)*n*m;
88if(map[i][j]==0){
89for(p=1;p<x;++p)
90 add(now+p+1,now+p+2,inf),add(now+p+1,T,1);
91 add(now+x+1,T,1);
92 }
93if(map[i][j]==1){
94 add(1,now+1,1);
95for(p=1;p<=n;++p)
96for(q=1;q<=m;++q)
97if(f[i][j][p][q])
98 add(now+1,((p-1)*m+q-1)*n*m+f[i][j][p][q]+1,1);
99 }
100 }
101return ISAP(1,T)==sum;
102}
103int main(){
104int i,j;
105 scanf("%d%d",&n,&m);
106for(i=1;i<=n;++i){
107 scanf("%s",&s);
108for(j=0;j<m;++j){
109if(s[j]==‘D‘) map[i][j+1]=0;
110if(s[j]==‘.‘) map[i][j+1]=1,sum+=1;
111if(s[j]==‘X‘) map[i][j+1]=2;
112 }
113 }
114for(i=1;i<=n;++i)
115for(j=1;j<=m;++j)
116if(map[i][j]==0)
117 bfs(i,j);
118for(i=1;i<=n;++i)
119for(j=1;j<=m;++j)
120if(!flag[i][j]&&map[i][j]==1){
121 printf("impossible\n");
122return0;
123 }
124int l=1,r=n*m,ans=inf;
125while(l<r){
126if(check(mid)) ans=min(ans,mid),r=mid;
127else l=mid+1;
128 }
129 printf("%d\n",ans);
130 }
原文：http://www.cnblogs.com/grhyxzc/p/5211111.html
内容总结
以上是互联网集市为您收集整理的C++之路进阶——最大流（紧急疏散）全部内容，希望文章能够帮你解决C++之路进阶——最大流（紧急疏散）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】