首页 > 搜索 > DFS搜索 > HDU 1733 Escape-网络流-[解题报告] C++
2013
12-21

HDU 1733 Escape-网络流-[解题报告] C++

Escape

问题描述 :

Loneknight hates attending class very much. Every time he is attending class, when he feel tiresome with the class, he start planning the shortest path he can escape from the classroom. Therefore, he can escape from classroom so quickly that he is always the first one escape from the classroom after the class finishes. He is very proud of this fact.

One day, loneknight is day dreaming in class, and planning the shortest path for escaping. Suddently, an issue come into his mind, if everyone in the classroom want to escape as soon as possible just as loneknight, what will happend? As a kind man, loneknight want to plan a strategy that will let everyone escape from the classroom with minimum time consume. But after dozens of minutes of consideration, loneknight find this problem so difficult for him.

Now, as the best friend of him, please design a algorithm to solve this problem for him. Note that, at every time unit, everyone can move seperately up, down, left, right one unit, or stay in the old position. In addtion, no one can move to a wall or out of the room, the only way to escape is go through a gate. Moreover, at every time unit, a position can only contain a person, including gates. That means if in time t, a person escape thourgh gate g, no one can go into g in time t, but can go into g in t + 1. Now, it’s your job to calculate the minimum time required to escape for everyone.

输入:

The input consists of several test cases. Each test case start with a line containing two number, n, m (1 < n, m <= 16), the rows and the columns of the room. Then n lines follow, each contain exact m characters, representing th type of unitin it. (. for empty place, X for human, # for wall, @ for gate). Input is end with EOF.

输出:

You have to print the shortest time needed for everyone escape from the roomin a single line for each case. (-1 if impossible)

样例输入:

4 4
.@..
.X..
....
....

4 4
.@..
.XX.
.XX.
..@.

4 4
.@..
.#..
#X#.
.#..

样例输出:

1
2
-1

1.拆点,对于第d天,每个点已被拆为d+1个点,下标代号成等差数列 公差n*m.

2.起始的时候,s向第0天的n*m中是人的点连条权值为1的边。

3.而后从小到大枚举每天,假设第t天,那么对于t-1天的点可以向四周扩展,或不动,向对应在第t天新加的点连条权为1的边,然后对第t天的n*m点,如果是出口则向汇点连条权值为1的边,然后从源点到汇点做网络流,如果ans等于人数,则break,return t。

4.对于没有解的情况,我是先dfs判断是否有解处理的。

比较挫,g++跑了125ms。

#include<cstring>
#include<cstdio>
#include<queue>
char mp[30][30];
int cnt,ans,head[30000],gap[30000],dis[30000],sum,vi[30][30];
const int inf=1<<30;
struct EDGE
{
	int to,f,nxt;
}edge[2000000];
int n,m,s,t,nn;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int di[][2]={1,0,-1,0,0,1,0,-1,0,0};
int min(int a,int b)
{
	return a<b?a:b;
}
int in(int x,int y)
{
	return x>=1&&x<=n&&y>=1&&y<=m&&mp[x][y]!='#';
}
void add(int a,int b,int c)
{
	edge[cnt].to=b;
	edge[cnt].f=c;
	edge[cnt].nxt=head[a];
	head[a]=cnt++;
	edge[cnt].to=a;
	edge[cnt].f=0;
	edge[cnt].nxt=head[b];
	head[b]=cnt++;
}
void init()
{
		cnt=ans=sum=0;
		memset(head,-1,sizeof(head));
		for(int i=1;i<=n;i++)
			scanf("%s",mp[i]+1);
		s=1,t=2;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			int num=(i-1)*m+j+2;
			if(mp[i][j]=='X')
			{
				sum++;
				add(s,num,1); 
			}
		}
		nn=2+n*m;
}
int dfs(int x,int y)
{
    vi[x][y]=1;
	if(mp[x][y]=='@')
	return 1;
	for(int i=0;i<4;i++)
	{
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(!in(xx,yy))
			continue;
		if(vi[xx][yy])
		continue;
		if(dfs(xx,yy))
		return 1;
	}
	return 0;
}
int ok()
{
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		memset(vi,0,sizeof(vi));
		if(mp[i][j]=='X'&&!dfs(i,j))
		return 1;
	}
	return 0;
}
int gfs(int x,int flow)
{
	if(x==t)
	return flow;
	int temp=flow,pos=nn-1,j;
	for(j=head[x];j!=-1;j=edge[j].nxt)
	{
		int y=edge[j].to;
		int c=edge[j].f;
		if(c>0&&dis[x]==dis[y]+1)
		{
			int temp_flow=gfs(y,min(temp,c));
			temp-=temp_flow;
			edge[j].f-=temp_flow;
			edge[j^1].f+=temp_flow;
			if(temp==0||dis[s]==nn)
			return flow-temp;
		}
		if(c>0&&pos>dis[y])
		pos=dis[y];
	}
	if(temp==flow)
	{
		if(!(--gap[dis[x]]))
		dis[s]=nn;
		else
		gap[dis[x]=pos+1]++;
	}
	return flow-temp;
}
int sap()
{
    int maxflow=0;
	memset(gap,0,sizeof(gap));
	memset(dis,0,sizeof(dis));
	gap[0]=nn;
	while(dis[s]<nn)
	{
		maxflow+=gfs(s,inf);
	}
	return maxflow;
}
int judge(int ti)
{
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		int u=(i-1)*m+j;
		u=(ti-1)*m*n+2+u;
		if(mp[i][j]=='#')
		continue;
		for(int k=0;k<5;k++)
		{
			int x=i+di[k][0];
			int y=j+di[k][1];
			int v=(x-1)*m+y;
			v=ti*m*n+2+v;
			if(!in(x,y))
			continue;
			add(u,v,1);
		}
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		int v=(i-1)*m+j;
		v=2+ti*m*n+v;
		if(mp[i][j]=='@')
		{
		 add(v,t,1);
      }
    }
	nn+=n*m;
	ans+=sap();
	return ans==sum;
}
int gao()
{
	if(sum==0)
	return 0;
	int ti=0;
	while(1)
	{
		ti++;
		if(judge(ti))
		break;
		//printf("%d",ti); 
//		printf("%d",ans);
	}
	return ti;
}
int main()
{
	while(2==scanf("%d%d",&n,&m))
	{
		init();
		if(ok())
		{
			printf("-1\n");
			continue;
		}
		printf("%d\n",gao());
	}
	return 0;
}

解题报告转自:http://blog.csdn.net/nash142857/article/details/7909386


  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  2. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。