2015
09-18

# 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

———————–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：当前新找出的这条路径的最大流量。

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

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

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

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

#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];
void init()
{
cnt=0;
}
{
e[cnt].u=a;
e[cnt].v=b;
e[cnt].flow=c;
e[cnt].w=1;

e[cnt].u=b;
e[cnt].v=a;
e[cnt].flow=0;
e[cnt].w=-1;
}
}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;
{
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);
}
treatment();
}
return 0;
}

1. 郭与王比，可能不止十万八千里，简直就是二条平行线，即不在同一个层面上。郭根本就不知民主为何物，而自以为是地把民主与宪制分割开来。王说的对极：宪政一定不是目的而是手段。也即民主是目的，宪政是手段。法治是民主其中的一个内容，宪政是法治的根本，所谓法治就是以宪

2. 郭与王比，可能不止十万八千里，简直就是二条平行线，即不在同一个层面上。郭根本就不知民主为何物，而自以为是地把民主与宪制分割开来。王说的对极：宪政一定不是目的而是手段。也即民主是目的，宪政是手段。法治是民主其中的一个内容，宪政是法治的根本，所谓法治就是以宪

3. 郭与王比，可能不止十万八千里，简直就是二条平行线，即不在同一个层面上。郭根本就不知民主为何物，而自以为是地把民主与宪制分割开来。王说的对极：宪政一定不是目的而是手段。也即民主是目的，宪政是手段。法治是民主其中的一个内容，宪政是法治的根本，所谓法治就是以宪

4. 郭与王比，可能不止十万八千里，简直就是二条平行线，即不在同一个层面上。郭根本就不知民主为何物，而自以为是地把民主与宪制分割开来。王说的对极：宪政一定不是目的而是手段。也即民主是目的，宪政是手段。法治是民主其中的一个内容，宪政是法治的根本，所谓法治就是以宪

5. 郭与王比，可能不止十万八千里，简直就是二条平行线，即不在同一个层面上。郭根本就不知民主为何物，而自以为是地把民主与宪制分割开来。王说的对极：宪政一定不是目的而是手段。也即民主是目的，宪政是手段。法治是民主其中的一个内容，宪政是法治的根本，所谓法治就是以宪

6. 郭与王比，可能不止十万八千里，简直就是二条平行线，即不在同一个层面上。郭根本就不知民主为何物，而自以为是地把民主与宪制分割开来。王说的对极：宪政一定不是目的而是手段。也即民主是目的，宪政是手段。法治是民主其中的一个内容，宪政是法治的根本，所谓法治就是以宪

7. 郭与王比，可能不止十万八千里，简直就是二条平行线，即不在同一个层面上。郭根本就不知民主为何物，而自以为是地把民主与宪制分割开来。王说的对极：宪政一定不是目的而是手段。也即民主是目的，宪政是手段。法治是民主其中的一个内容，宪政是法治的根本，所谓法治就是以宪

8. 郭与王比，可能不止十万八千里，简直就是二条平行线，即不在同一个层面上。郭根本就不知民主为何物，而自以为是地把民主与宪制分割开来。王说的对极：宪政一定不是目的而是手段。也即民主是目的，宪政是手段。法治是民主其中的一个内容，宪政是法治的根本，所谓法治就是以宪

9. 郭与王比，可能不止十万八千里，简直就是二条平行线，即不在同一个层面上。郭根本就不知民主为何物，而自以为是地把民主与宪制分割开来。王说的对极：宪政一定不是目的而是手段。也即民主是目的，宪政是手段。法治是民主其中的一个内容，宪政是法治的根本，所谓法治就是以宪

10. 郭与王比，可能不止十万八千里，简直就是二条平行线，即不在同一个层面上。郭根本就不知民主为何物，而自以为是地把民主与宪制分割开来。王说的对极：宪政一定不是目的而是手段。也即民主是目的，宪政是手段。法治是民主其中的一个内容，宪政是法治的根本，所谓法治就是以宪

11. 郭与王比，可能不止十万八千里，简直就是二条平行线，即不在同一个层面上。郭根本就不知民主为何物，而自以为是地把民主与宪制分割开来。王说的对极：宪政一定不是目的而是手段。也即民主是目的，宪政是手段。法治是民主其中的一个内容，宪政是法治的根本，所谓法治就是以宪

12. 郭与王比，可能不止十万八千里，简直就是二条平行线，即不在同一个层面上。郭根本就不知民主为何物，而自以为是地把民主与宪制分割开来。王说的对极：宪政一定不是目的而是手段。也即民主是目的，宪政是手段。法治是民主其中的一个内容，宪政是法治的根本，所谓法治就是以宪

13. ᓭ原单正品Stella McCartneyPhilipp Plein（菲利普?普莱因）Vero CwloMBTValentino(华伦天奴)TOMS(汤姆布鞋)www.wx31.com