首页 > ACM题库 > HDU-杭电 > HDU 4807-Lunch Time-最短路径-[解题报告]HOJ
2015
09-18

HDU 4807-Lunch Time-最短路径-[解题报告]HOJ

Lunch Time

问题描述 :

The campus of Nanjing University of Science and Technology can be viewed as a graph with N vertexes and M directed edges (vertexes are numbered from 0 to N – 1). Each edge has the same length 1. Every day, there are K students walking to the dinning-hall (vertex N – 1) from the teaching building (vertex 0) at lunch time. They all want reach the dinning-hall as soon as possible. However, each edge can only serve at most ci students at any time. Can you make arrangements for students, so that the last student can reach the dinning-hall as soon as possible? (It is assumed that the speed of the students is 1 edge per unit time)

输入:

There are several test cases, please process till EOF.
The first line of each test case contains three integer N(2 <= N <= 2500), M(0 <= M <= 5000), K(0 <= K <= 109). Then follows M lines, each line has three numbers ai, bi, ci(0 <= ci <= 20), means there is an edge from vertex ai to bi with the capacity ci.

输出:

There are several test cases, please process till EOF.
The first line of each test case contains three integer N(2 <= N <= 2500), M(0 <= M <= 5000), K(0 <= K <= 109). Then follows M lines, each line has three numbers ai, bi, ci(0 <= ci <= 20), means there is an edge from vertex ai to bi with the capacity ci.

样例输入:

5 6 4
0 1 2
0 3 1
1 2 1
2 3 1
1 4 1
3 4 2
3 3 10
0 1 1
1 2 1
0 2 1
2 0 1

样例输出:

3
6
No solution

题意:给你n个点,m条边。0点是教学楼,n-1点是食堂,每一条路的长度是单位1,每一条路有一个容量flow表示这一条路在任意单位时间段里最多只能同时有flow个人,一个人从node_a走到node_b的时间是单位1。现在有k个人,问你最少要多少时间,这些k个人都可以到食堂。


想法:首先0到n-1的时间就是0到n-1的距离。现在要让k个人全部通过,肯定是多走耗时最少的路径,也就是没有公共边的最短路径(最短路*),例如:有一条路径耗时1,容量1,另一条路径耗时5,容量100,当k=4时,最少耗时是4,当k=100时,最少耗时是5,则他们两个条路通过的人数分别是5和95。


现在把问题更加的具体一点,现在找出了p条最短路*,从上到下按照耗时升序排列,如果这里的p条路径我都要用到,也就是说,每条路上都需要人,这里假设人很多(意思就是所有的路不能装下着k个人)。现在k个人在0这个点上,他们的第一波(当前p条路径能够存下的最大的人数)一起往n-1点跑,我们可以知道当最长的那条路径的人一到达n-1点的时候,已经有下一波人在所有其他的路径上出发了。当最长路径的第一波人到达以后,那么p条路径饱满,那么这是还需要的时间t=(剩余人数/单位时间整个p条路径可以通过的人数)。

现在我们知道了这一点,可以想到,枚举图的前p个最短路*,按照上面的方法进行计算。这个不是找k短路问题,因为这里的最短路之间是不能有重边的。所以这里用到费用流,因为费用流有一个性质:每一次找的费用最短的路的费用是依次递增的,因为他通过流量的变化实现了,最短路之间没有公共边的条件。而且我们还可以知道,一条可行的最短路*的最多可同行的人数,即这条路径的最小流量,也可以知道跑完这条路径的时间。

———————–SKTelecom T1————————

现在用公式来实现之前的文字叙述。

*1*.当最长的路径的第一波人到达之后,总人数还剩多少人:

k-=(dis[t]-last_path_len)*passnum_per_sec+flowmin

dis[t]:当前这条边从0到n-1的距离。

last_path_len:除了现在的这条路径,之前的所有路径中长的最长的,因为是有序的路径寻找,所以就是上一条路径的长度。

passnum_per_sec:除了现在的这条路径,之前的所有路径里面的人同时运动,每秒可以通过的人数,这不就是之前所有的路径的流量和吗!!!

flowmin:当前新找出的这条路径的最大流量。

公式的解析:在我进行所有路径全部都饱满之前,我要去除一些人,那就是新增的路径中第一波人要先到n-1点,这样之后的人跟上,这不就使得当前这条新边饱满了吗!!!但是有一点要注意,但你跑新边的时候,其他路的人还是继续在跑的。我们需要知道这段时间,跑过n-1点的人数,他由两个部分组成,1.之前的边一起跑tim(新路比上一条路多的长度的时间)时间,2.新路在1中的那段时间里会有人跑到n-1点,人数就是这条路径的最大流flowmin。

*2*.第1部分我们找到了一个可以所有路径,开满流一起冲的条件了,那么接下来就是算总时间了:

total_time=dis[t]+k/(passnum_per_sec+flowmin)

加上dis[t]的原因是满足*1*的条件需要的时间,所有路达到满流。

k:这里的k已经是剩余的人数了。

pass_per_sec+flowmin:当前加上新边,所有的边一起跑满流,那么此时的满流就是新边的最大流加上之前所有边的最大流。

此题到这里就结束了,很开心,自己真的学到了很多。


Lunch Time


#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue> 
#include<cmath>
#define inf 0x7fffffff
using namespace std; 
const int nodes=2500+50;
const int edges=10000+50;
int s,t;
int n,m,k;
int pre[nodes],dis[nodes];
class node
{
	public:
		int u,v,next,flow,w;
};
class E
{
	public:
		node e[edges];
		int head[nodes],cnt;
		void init()
		{
			memset(head,-1,sizeof(head));
			cnt=0;
		}
		void add(int a,int b,int c)
		{
			e[cnt].u=a;
			e[cnt].v=b;
			e[cnt].flow=c;
			e[cnt].w=1;
			e[cnt].next=head[a];
			head[a]=cnt++;
		
			e[cnt].u=b;
			e[cnt].v=a;
			e[cnt].flow=0;
			e[cnt].w=-1;
			e[cnt].next=head[b];
			head[b]=cnt++;
		}
}e1;
int spfa()
{
	int vis[nodes]={0};
	queue<int>q;
	while(!q.empty()) q.pop();
	memset(pre,-1,sizeof(pre)); 
	for(int i=0;i<n;i++)
	dis[i]=inf;
	vis[s]=1;
	dis[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=e1.head[u];i+1;i=e1.e[i].next)
		{
			int v=e1.e[i].v;
			if(dis[v]>dis[u]+e1.e[i].w&&e1.e[i].flow>0)
			{
				dis[v]=dis[u]+e1.e[i].w;
				pre[v]=i;
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return pre[t]!=-1;
}
void treatment()
{
	s=0;t=n-1;
	int last_path_len=0,pessnum_per_sec=0;
	int res=k,ans=inf;
	if(res==0)
	{
		printf("0\n");
		return;
	}
	while(spfa())
	{
		int minn=inf;
		for(int i=pre[t];i!=-1;i=pre[e1.e[i].u])
		{
			if(e1.e[i].flow<minn) minn=e1.e[i].flow;
		}
		for(int i=pre[t];i!=-1;i=pre[e1.e[i].u])
		{
			e1.e[i].flow-=minn;
			e1.e[i^1].flow+=minn;
		}
		res-=(dis[t]-last_path_len)*pessnum_per_sec+minn;
		last_path_len=dis[t];
		pessnum_per_sec+=minn;
		int temp=res;
		if(temp<0) temp=0;
		int n_ans=last_path_len+(int)ceil(1.0*temp/pessnum_per_sec);
		if(n_ans<ans) ans=n_ans;
		if(res<=0) break;
	}
	if(ans==inf) printf("No solution\n");
	else printf("%d\n",ans);
}
int main()
{
	while(~scanf("%d%d%d",&n,&m,&k))
	{
		e1.init();
		for(int i=1;i<=m;i++)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			e1.add(a,b,c);
		}
		treatment();
	}
	return 0;
}

参考:http://blog.csdn.net/triple_wdf/article/details/49764827