題意：
? ? ?給你一個有向圖，每條邊上都有每一時刻的最大流量，有k個人在點0，他們要去點n-1，問你最晚到達的那個人最快要多久。


思路：
? ? ?這個題目做了很多次，用過費用流，也用過最大流，結果都不行，怎么說的，這道題目用該是借助費用流的找新路徑去枚舉，可以說是費用流變形吧，首先我們一定要明白一點，就是時間的影響，單純的最大流如果在時間的基礎上考慮沒什么意義，而費用流呢，我們想象一下，如果把時間設成費用那么我們就可以吧流量和時間結合起來了，在費用流的過程中我們要知道，他每一次都是根據最短路去找新的路徑的，也就是說路徑在費用上來說是遞增的（流量不一定），那么我們就可以根據這個特點來枚舉一那些路徑來過人，要明白，如果起點到終點有兩條邊，一條很近，一條很遠，有可能大家都走近的路徑（寧可排隊走），也不走遠的（所以直接最大流是錯了），那么我們就可以枚舉路徑了，路徑可以直接用費用流每次的路徑，因為時間遞增的，對于每一次我們能過的人是多少呢？這個地方很關鍵，對于每一條路徑來說，如果當前的路徑a距離是10，流量是15，那么當時間大于10的時候，每過一個時間單位，路徑a都可以再過15個人，所以當前的時間段的總人數是
之前的總人數+（當前長度-上一個長度）* 上一個的總流量 + 當前流量
那么如果現在當前這一部之前的所有路徑當路徑要花費的時間是多少呢
now = 當前長度+剩余的路徑長度/當前總流量 ?向上取整

這樣比較now和ans更新答案就行了，還有一個地方要明確，就是當總人數超過全圖的最大流的時候答案就是 費用流中最長的路徑 + 總人數/全圖最大流 向上取整，這個地方不用特判，上面的想法里面包括在這里，說了只是為了便于理解。

#include<stdio.h> #include<string.h> #include<queue> #include<math.h>#define N_node 2500 + 50 #define N_edge 10000 + 100 #define INF 2000000000 using namespace std;typedef struct {int from ,to ,next ,cost ,flow; }STAR;STAR E[N_edge]; int list[N_node] ,tot; int mer[N_edge] ,s_x[N_node];void add(int a ,int b ,int c ,int d) {E[++tot].from = a;E[tot].to = b;E[tot].cost = c;E[tot].flow = d;E[tot].next = list[a];list[a] = tot; }bool spfa(int s ,int t ,int n) {int mark[N_node] = {0};for(int i = 0 ;i <= n ;i ++)s_x[i] = INF;queue<int>q;q.push(s);mark[s] = 1 ,s_x[s] = 0;memset(mer ,255 ,sizeof(mer));while(!q.empty()){int xin ,tou;tou = q.front();q.pop();mark[tou] = 0;for(int k = list[tou] ;k ;k = E[k].next){xin = E[k].to;if(s_x[xin] > s_x[tou] + E[k].cost && E[k].flow){ s_x[xin] = s_x[tou] + E[k].cost;mer[xin] = k;if(!mark[xin]){mark[xin] = 1;q.push(xin);}}}}return mer[t] != -1; }int M_C_Flow(int s ,int t ,int n ,int k) {if(!k) return 0;int minflow ,sum_peo = k ,now_peo = 0 ,list_time = 0 ,ans = INF;while(spfa(s ,t ,n)){ minflow = INF;for(int i = mer[t] ;i + 1 ;i = mer[E[i].from])if(minflow > E[i].flow) minflow = E[i].flow;for(int i = mer[t] ;i + 1 ;i = mer[E[i].from])E[i].flow -= minflow ,E[i^1].flow += minflow;sum_peo -= (s_x[t] - list_time) * now_peo + minflow;list_time = s_x[t] ,now_peo += minflow;int now = s_x[t] + (int)ceil((1.0 * (sum_peo < 0 ? 0 : sum_peo ))/now_peo);if(ans > now) ans = now;if(sum_peo < 1) break;}return ans; }int main () {int n ,m ,k ,i ,a ,b ,c;while(~scanf("%d %d %d" ,&n ,&m ,&k)){memset(list ,0 ,sizeof(list));tot = 1;for(i = 1 ;i <= m ;i ++){scanf("%d %d %d" ,&a ,&b ,&c);a ++ ,b ++;add(a ,b ,1 ,c) ,add(b ,a ,-1 ,0);}int ans = M_C_Flow(1 ,n ,n ,k);ans == INF ? puts("No solution"):printf("%d\n" ,ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu4807枚举费用流的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。