首页 > 代码库 > HDU 3036 拆点二分最大流
HDU 3036 拆点二分最大流
Escape
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 584 Accepted Submission(s): 117
Problem Description
R‘s girl friend D is on military training somewhere near Harbin. She feels bad every day and night. She complains about every terrible thing to R. And sometimes she would wail loudly that she had hurt her foot.
R has a motto, which is "Finding her is my lifetime fate, yet cherishing her is my daily job." So he made a plan, which called "Prison Break", as you know, the same with the famouse American play.
R found out that there were several holes on the wire netting which surrounds the military camp. Or maybe, just R did that. Whatever, R told this to his girl friend D. D gathered the girl comrades, and they decided to escape this night. To help to make the escape safe, R investigated the camp again. And something worse found was soldiers walked guard even in the night. But the good news was they drunk much every night and they were dozing off every night.
The girls‘ escape, will not make no sound. Once they take action, the evil commander will send his soldiers(not the drunk ones of course) to stop them. You can assume that the soldiers will get there after T seconds. So if they take more time than T, they will get caught.
Initially, there is one person on every empty square in the camp and these persons should move to a hole on the wire netting to exit. They can move one square per second to the North, South, East or West. While escaping, multiple persons can be on a single square. The holes are narrow, however, and only one person can leave through a hole per second.
Now, R and D wants to know whether this action will be successful.If successful, then how much time it will take to get out from the camp.
R has a motto, which is "Finding her is my lifetime fate, yet cherishing her is my daily job." So he made a plan, which called "Prison Break", as you know, the same with the famouse American play.
R found out that there were several holes on the wire netting which surrounds the military camp. Or maybe, just R did that. Whatever, R told this to his girl friend D. D gathered the girl comrades, and they decided to escape this night. To help to make the escape safe, R investigated the camp again. And something worse found was soldiers walked guard even in the night. But the good news was they drunk much every night and they were dozing off every night.
The girls‘ escape, will not make no sound. Once they take action, the evil commander will send his soldiers(not the drunk ones of course) to stop them. You can assume that the soldiers will get there after T seconds. So if they take more time than T, they will get caught.
Initially, there is one person on every empty square in the camp and these persons should move to a hole on the wire netting to exit. They can move one square per second to the North, South, East or West. While escaping, multiple persons can be on a single square. The holes are narrow, however, and only one person can leave through a hole per second.
Now, R and D wants to know whether this action will be successful.If successful, then how much time it will take to get out from the camp.
Input
Multiple cases.
Each test case has the following format:
One line with three integers r, c and T , separated by a single space, satisfying 3 <= r, c <= 12: the size of the camp
Then r lines with c characters descripes the camp.
Girls represented by a ‘.‘ . Drunk soldiers and the wire netting represented by an ‘X‘, you can assume that the drunk ones will not move even one square. And the hole is ‘E‘, meaning an exit to the girls.
Input file ends with EOF.
Each test case has the following format:
One line with three integers r, c and T , separated by a single space, satisfying 3 <= r, c <= 12: the size of the camp
Then r lines with c characters descripes the camp.
Girls represented by a ‘.‘ . Drunk soldiers and the wire netting represented by an ‘X‘, you can assume that the drunk ones will not move even one square. And the hole is ‘E‘, meaning an exit to the girls.
Input file ends with EOF.
Output
A single line with the minimal escape time in seconds, if escape is possible, or "impossible", if it is not.
Sample Input
5 5 3 XXEXX X...X E...X X...E XXXXX
Sample Output
3
Source
2009 Multi-University Training Contest 13 - Host by HIT
一个最大为12*12的进行，‘X‘,代表不可经过的格子，‘.‘代表女孩，‘E‘代表出口，每一个女孩一秒内可以到达向上下左右可以到达的格子，
一个格子可以容纳多个女孩，但是一个出口一秒内只能出去一个人，给定时间T，问所有女孩是否可以出去，假如可以的话，求最短时间。
一开始以为二分时间，只要女孩可以到达某一个出口，直接连边最大流，后来发现时错的，但是HDU数据弱了，还是可以ac的，
后来发现有问题，假如时间上限是5，有5个人在4的时候到达出口，那么显然是出不去的。
因此需要拆点，每一个入口按时间拆点，然后源点向女孩连流量为1的边，每一个出口点向汇点连流量为1的边，然后女孩向对应出口时间点连
流量为1的时间点，还有就是假如当女孩到达出口这个时间点已经有人了，那么需要等到下一个时间点，向下一个时间点连流量为无穷大的边，
然后跑最大流，判断是否漫流。
sap代码：
/* ***********************************************
Author :_rabbit
Created Time :2014/5/3 20:55:13
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=200000;
const int maxm=1002000;
struct Edge{
int next,to,cap;
Edge(){};
Edge(int _next,int _to,int _cap){
next=_next;to=_to;cap=_cap;
}
}edge[maxm];
int head[maxn],tol,dep[maxn],gap[maxn];
void addedge(int u,int v,int flow){
edge[tol]=Edge(head[u],v,flow);head[u]=tol++;
edge[tol]=Edge(head[v],u,0);head[v]=tol++;
}
int Q[maxn];
void bfs(int start,int end){
memset(dep,-1,sizeof(dep));
memset(gap,0,sizeof(gap));
gap[0]++;int front=0,rear=0;
dep[end]=0;Q[rear++]=end;
while(front!=rear){
int u=Q[front++];front%=maxn;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;if(dep[v]==-1)
Q[rear++]=v,dep[v]=dep[u]+1,gap[dep[v]]++;
rear%=maxn;
//if(dep[u]<0||dep[v]<0)cout<<"PPPPP"<<endl;
}
}
}
int cur[maxn],S[maxn];
int sap(int s,int t,int N){
int res=0;bfs(s,t);
int top=0,u=s,i;
memcpy(cur,head,sizeof(head));
while(dep[s]<N){
if(u==t){
int temp=INF,id;
for( i=0;i<top;i++)
if(temp>edge[S[i]].cap)
temp=edge[S[i]].cap,id=i;
for( i=0;i<top;i++)
edge[S[i]].cap-=temp,edge[S[i]^1].cap+=temp;
res+=temp;top=id;u=edge[S[top]^1].to;
}
if(u!=t&&gap[dep[u]-1]==0)break;
for( i=cur[u];i!=-1;i=edge[i].next)
if(edge[i].cap&&dep[u]==dep[edge[i].to]+1)break;
if(i!=-1)cur[u]=i,S[top++]=i,u=edge[i].to;
else{
int MIN=N;
for( i=head[u];i!=-1;i=edge[i].next)
if(edge[i].cap&&MIN>dep[edge[i].to])
MIN=dep[edge[i].to],cur[u]=i;
// if(MIN==N)cout<<"hahhaaahha"<<endl;
--gap[dep[u]];++gap[dep[u]=MIN+1];
if(u!=s)u=edge[S[--top]^1].to;
}
}
return res;
}
char mp[20][20];
int id[20][20],dist[200][200];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int main()
{
// freopen("date.in","r",stdin);
//freopen("data.out","w",stdout);
int r,c,T;
while(~scanf("%d%d%d",&r,&c,&T)){
int girl=0,E=0;memset(id,-1,sizeof(id));
for(int i=0;i<r;i++){
scanf("%s",mp[i]);
for(int j=0;j<c;j++){
if(mp[i][j]==‘.‘)girl++;
if(mp[i][j]==‘E‘)E++;
}
}
if(!E){
puts("impossible");continue;//没有出口。
}
if(!girl){
puts("0");continue;//没有女孩
}
int c1=0,c2=0;
for(int i=0;i<r;i++)
for(int j=0;j<c;j++){
if(mp[i][j]==‘.‘)id[i][j]=(++c1)+E;//女孩编号
if(mp[i][j]==‘E‘)id[i][j]=++c2;//出口编号。
}
int flag=1;
//cout<<"hhhhh"<<endl;
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
if(mp[i][j]==‘E‘){
int s=id[i][j];
for(int k=0;k<160;k++)dist[s][k]=INF;
dist[s][s]=0;
queue<pair<int,int> > q;q.push(make_pair(i,j));
while(!q.empty()){
pair<int,int> u=q.front();q.pop();
int x=u.first,y=u.second;
int gg=id[x][y];
for(int t=0;t<4;t++){
int tx=x+dx[t];
int ty=y+dy[t];
if(tx>=0&&tx<r&&ty>=0&&ty<c&&mp[tx][ty]==‘.‘){
int dd=id[tx][ty];
if(dist[s][dd]>dist[s][gg]+1){
dist[s][dd]=dist[s][gg]+1;
q.push(make_pair(tx,ty));
}
}
}
}
}
int left=0,right=150;
while(left<right){
int mid=(left+right)/2;
memset(head,-1,sizeof(head));tol=0;
for(int i=E+1;i<=E+girl;i++)//枚举每一个女孩
for(int j=1;j<=E;j++)//枚举每一个出口
if(dist[j][i]<=mid)
addedge(i,150+(j-1)*mid+dist[j][i],1);
for(int i=E+1;i<=E+girl;i++)addedge(0,i,1);//源点向每一个女孩连流量为1的边
for(int i=1;i<=E;i++)
for(int j=1;j<=mid;j++){
addedge(150+(i-1)*mid+j,E*mid+151,1);
if(j!=mid)
addedge(150+(i-1)*mid+j,150+(i-1)*mid+j+1,INF);
}
int ans=sap(0,E*mid+151,100000);
if(ans<girl)left=mid+1;
else right=mid;
}
if(left>T){
puts("impossible");continue;
}
printf("%d\n",left);
}
return 0;
}
dinic代码：
/* ***********************************************
Author :_rabbit
Created Time :2014/5/3 20:55:13
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=50010;
const int maxm=400010;
struct Edge{
int to,next,cap;
Edge(){};
Edge(int _next,int _to,int _cap){
next=_next;to=_to;cap=_cap;
}
}edge[maxm];
int head[maxn],tol,dep[maxn],cur[maxn],n;
void addedge(int u,int v,int flow){
edge[tol]=Edge(head[u],v,flow);head[u]=tol++;
edge[tol]=Edge(head[v],u,0);head[v]=tol++;
}
int Q[maxn];
bool bfs(int start,int end){
memset(dep,-1,sizeof(dep));
int front=0,rear=0;
dep[start]=0;Q[rear++]=start;
while(front!=rear){
int u=Q[front++];
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;if(dep[v]==-1&&edge[i].cap){
Q[rear++]=v,dep[v]=dep[u]+1;
if(v==end)return 1;
}
}
}
return 0;
}
int dinic(int s,int t){
int i,res=0,top;
int S[maxn],cur[maxn];
while(bfs(s,t)){
memcpy(cur,head,sizeof(head));
int u=s;top=0;
while(1){
if(u==t){
int min=INF,loc;
for(int i=0;i<top;i++)if(min>edge[S[i]].cap)
min=edge[S[i]].cap,loc=i;
for(int i=0;i<top;i++)
edge[S[i]].cap-=min,edge[S[i]^1].cap+=min;
res+=min;top=loc;u=edge[S[top]^1].to;
}
for(int i=cur[u];i!=-1;cur[u]=i=edge[i].next)
if(edge[i].cap&&dep[u]+1==dep[edge[i].to])break;
if(cur[u]!=-1)S[top++]=cur[u],u=edge[cur[u]].to;
else{
if(top==0)break;
dep[u]=-1;u=edge[S[--top]^1].to;
}
}
}
return res;
}
char mp[20][20];
int id[20][20],dist[200][200];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int main()
{
// freopen("date.in","r",stdin);
//freopen("data.out","w",stdout);
int r,c,T;
while(~scanf("%d%d%d",&r,&c,&T)){
int girl=0,E=0;memset(id,-1,sizeof(id));
for(int i=0;i<r;i++){
scanf("%s",mp[i]);
for(int j=0;j<c;j++){
if(mp[i][j]==‘.‘)girl++;
if(mp[i][j]==‘E‘)E++;
}
}
if(!E){
puts("impossible");continue;//没有出口。
}
if(!girl){
puts("0");continue;//没有女孩
}
int c1=0,c2=0;
for(int i=0;i<r;i++)
for(int j=0;j<c;j++){
if(mp[i][j]==‘.‘)id[i][j]=(++c1)+E;//女孩编号
if(mp[i][j]==‘E‘)id[i][j]=++c2;//出口编号。
}
int flag=1;
//cout<<"hhhhh"<<endl;
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
if(mp[i][j]==‘E‘){
int s=id[i][j];
for(int k=0;k<160;k++)dist[s][k]=INF;
dist[s][s]=0;
queue<pair<int,int> > q;q.push(make_pair(i,j));
while(!q.empty()){
pair<int,int> u=q.front();q.pop();
int x=u.first,y=u.second;
int gg=id[x][y];
for(int t=0;t<4;t++){
int tx=x+dx[t];
int ty=y+dy[t];
if(tx>=0&&tx<r&&ty>=0&&ty<c&&mp[tx][ty]==‘.‘){
int dd=id[tx][ty];
if(dist[s][dd]>dist[s][gg]+1){
dist[s][dd]=dist[s][gg]+1;
q.push(make_pair(tx,ty));
}
}
}
}
}
int left=0,right=150;
while(left<right){
int mid=(left+right)/2;
memset(head,-1,sizeof(head));tol=0;
for(int i=E+1;i<=E+girl;i++)//枚举每一个女孩
for(int j=1;j<=E;j++)//枚举每一个出口
if(dist[j][i]<=mid)
addedge(i,150+(j-1)*mid+dist[j][i],1);
for(int i=E+1;i<=E+girl;i++)addedge(0,i,1);//源点向每一个女孩连流量为1的边
for(int i=1;i<=E;i++)
for(int j=1;j<=mid;j++){
addedge(150+(i-1)*mid+j,E*mid+151,1);
if(j!=mid)
addedge(150+(i-1)*mid+j,150+(i-1)*mid+j+1,INF);
}
int ans=dinic(0,E*mid+151);
if(ans<girl)left=mid+1;
else right=mid;
}
if(left>T){
puts("impossible");continue;
}
printf("%d\n",left);
}
return 0;
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。