Lunch Time(费用流变型题，以时间为费用)

Lunch Time

http://acm.hdu.edu.cn/showproblem.php?pid=4807

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 782 Accepted Submission(s): 183

Problem Description

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)

Input

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 <= 10⁹). Then follows M lines, each line has three numbers a_i, b_i, c_i(0 <= c_i <= 20), means there is an edge from vertex a_i to b_i with the capacity c_i.

Output

For each test case, print an integer represents the minimum time. If the requirements can not be met, print “No solution”(without quotes) instead.

Sample Input

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

Sample Output

No solution

Source

2013ACM/ICPC亚洲区南京站现场赛——题目重现

参考博客：https://blog.csdn.net/u013761036/article/details/38268335

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<cmath>
  7 using namespace std;
  8 
  9 const int INF=0x3f3f3f3f;
 10 const int N=500005;
 11 const int M=500005;
 12 int top;
 13 int dist[N],pre[N];
 14 bool vis[N];
 15 int c[N];
 16 int maxflow;
 17 
 18 struct Vertex{
 19     int first;
 20 }V[N];
 21 struct Edge{
 22     int v,next;
 23     int cap,flow,cost;
 24 }E[M];
 25 
 26 void init(int n){
 27     for(int i=0;i<=n;i++){
 28         V[i].first=-1;
 29     }
 30     top=0;
 31     maxflow=0;
 32 }
 33 
 34 void add_edge(int u,int v,int c,int cost){
 35     E[top].v=v;
 36     E[top].cap=c;
 37     E[top].flow=0;
 38     E[top].cost=cost;
 39     E[top].next=V[u].first;
 40     V[u].first=top++;
 41 }
 42 
 43 void add(int u,int v,int c,int cost){
 44     add_edge(u,v,c,cost);
 45     add_edge(v,u,0,-cost);
 46 }
 47 
 48 bool SPFA(int s,int t,int n){
 49     int i,u,v;
 50     queue<int>qu;
 51     for(i=0;i<=n;i++){
 52         dist[i]=INF;
 53         vis[i]=false;
 54         c[i]=0;
 55         pre[i]=-1;
 56     }
 57     vis[s]=true;
 58     c[s]++;
 59     dist[s]=0;
 60     qu.push(s);
 61     while(!qu.empty()){
 62         u=qu.front();
 63         qu.pop();
 64         vis[u]=false;
 65         for(i=V[u].first;~i;i=E[i].next){
 66             v=E[i].v;
 67             if(E[i].cap>E[i].flow&&dist[v]>dist[u]+E[i].cost){
 68                 dist[v]=dist[u]+E[i].cost;
 69                 pre[v]=i;
 70                 if(!vis[v]){
 71                     c[v]++;
 72                     qu.push(v);
 73                     vis[v]=true;
 74                     if(c[v]>n){
 75                         return false;
 76                     }
 77                 }
 78             }
 79         }
 80     }
 81     if(dist[t]==INF){
 82         return false;
 83     }
 84     return true;
 85 }
 86 
 87 int MCMF(int s,int t,int n,int k){
 88     if(k==0) return 0;////////////*******************////
 89     int d;
 90     int i,mincost;
 91     mincost=0;
 92     int ans=INF;
 93     int sum_peo=k,now_peo=0,list_time=0;
 94     while(SPFA(s,t,n)){
 95         d=INF;
 96         for(i=pre[t];~i;i=pre[E[i^1].v]){
 97             d=min(d,E[i].cap-E[i].flow);
 98         }
 99         maxflow+=d;
100         for(i=pre[t];~i;i=pre[E[i^1].v]){
101             E[i].flow+=d;
102             E[i^1].flow-=d;
103         }
104         mincost+=dist[t]*d;
105         sum_peo-=(dist[t]-list_time)*now_peo+d;
106         list_time=dist[t],now_peo+=d;
107         int now=dist[t]+(int)ceil((1.0*(sum_peo<0?0:sum_peo))/now_peo);
108         if(ans>now) ans=now;
109         if(sum_peo<1) break;
110     }
111     return ans;
112 }
113 
114 int main(){
115     int n,m,k;
116     int v,u,w,c;
117     int s,t;
118     while(~scanf("%d %d %d",&n,&m,&k)){
119         s=0,t=n-1;
120         init(n);
121         for(int i=1;i<=m;i++){
122             scanf("%d %d %d",&v,&u,&c);
123             add(v,u,c,1);
124         }
125         int ans=MCMF(s,t,n,k);
126         if(ans==INF) printf("No solution
");
127         else printf("%d
",ans);
128     }
129 }
130 /*
131 题意：
132     给你一个有向图，每条边上都有每一时刻的最大流量，有k个人在点0，
133     他们要去点n-1，问你最晚到达的那个人最快要多久。
134 思路：
135     这道题目用该是借助费用流的找新路径去枚举，可以说是费用流变形吧，
136     首先我们一定要明白一点，就是时间的影响，单纯的最大流如果在时间的基础上考虑没什么意义，
137     而费用流呢，我们想象一下，如果把时间设成费用那么我们就可以吧流量和时间结合起来了，
138     在费用流的过程中我们要知道，他每一次都是根据最短路去找新的路径的，
139     也就是说路径在费用上来说是递增的（流量不一定），
140     那么我们就可以根据这个特点来枚举一那些路径来过人，
141     要明白，如果起点到终点有两条边，一条很近，一条很远，
142     有可能大家都走近的路径（宁可排队走），也不走远的（所以直接最大流是错了），
143     那么我们就可以枚举路径了，路径可以直接用费用流每次的路径，因为时间递增的，
144     对于每一次我们能过的人是多少呢？这个地方很关键，对于每一条路径来说，
145     如果当前的路径a距离是10，流量是15，那么当时间大于10的时候，每过一个时间单位，路径a都可以再过15个人，
146     所以当前的时间段的总人数是之前的总人数+（当前长度-上一个长度）* 上一个的总流量 + 当前流量
147     那么如果现在当前这一部之前的所有路径当路径要花费的时间是多少呢
148     now = 当前长度+剩余的路径长度/当前总流量  向上取整
149     这样比较now和ans更新答案就行了，
150     还有一个地方要明确，就是当总人数超过全图的最大流的时候答案就是
151     费用流中最长的路径 + 总人数/全图最大流 向上取整，
152     这个地方不用特判，上面的想法里面包括在这里，说了只是为了便于理解。
153 
154 */

View Code