hdu 4807（网络流 + 贪心）

题意：

　　n个点（0 到 n-1）， m条边，每条边花费都是1，容量不同，有k个人在0点，问，最少需要多少时间所有人能走到点n-1

解决：

　　建图，跑费用流的过程中贪心一下。

　　策略如下：

　　　　因为跑费用流的时候，每次增广路径的花费是递增的，假设按顺序找出了3条增广路径，w1, w2, w3，花费递增，容量未知，如果最优方案一定是，全部从w1走，或者尽量从w1和w2走，或者是3条路同时走。例子1，假设有一条增广路径，花费1，流量1，另一条增广路径，花费10，容量1000，只有5个人，解决方案当然是所有人都从花费少的路径走。答案是5；例子2，两条路径花费1，容量1，花费5容量10，有20个人，那么结果应该是6。

　　有一个很重要的性质，假设这条路的花费是x，流量是y，那么x秒之后，每秒钟这条路都能通过y人。、

　　所以我们每找到一条增广路的时候，就假设只用这条路以及之前的路。维护一个最小值，即为答案。

  1 #include <bits/stdc++.h>
  2 
  3 const int MAXN = 2600;
  4 const int MAXM = 100000;
  5 const int INF = 0x3f3f3f3f;
  6 
  7 struct Edge {
  8     int u, v, cap, cost, next;
  9     Edge() {}
 10     Edge(int _u, int _v, int _cap, int _cost, int _next)
 11     {
 12         u = _u;
 13         v = _v;
 14         cap = _cap;
 15         cost = _cost;
 16         next = _next;
 17     }
 18 }edge[MAXM];
 19 int tot;
 20 int head[MAXN];
 21 int n, m, k;
 22 int dist[MAXN];
 23 int pre[MAXN];
 24 bool in_que[MAXN];
 25 
 26 bool spfa(int src, int sink)
 27 {
 28     for (int i = 1; i <= n; ++ i) {
 29         dist[i] = INF;
 30     }
 31     memset(pre, 0, sizeof pre);
 32     memset(in_que, false, sizeof in_que);
 33     std::queue<int> que;
 34     que.push(src);
 35     dist[src] = 0;
 36     in_que[src] = true;
 37 
 38     while (que.empty() == false) {
 39         int u = que.front();
 40         que.pop();
 41         in_que[u] = false;
 42         for (int i = head[u]; i; i = edge[i].next) {
 43             int v = edge[i].v;
 44             int cost = edge[i].cost;
 45             if (edge[i].cap > 0 && dist[v] > dist[u] + cost) {
 46                 pre[v] = i;
 47                 dist[v] = dist[u] + cost;
 48                 if (in_que[v] == false) {
 49                     que.push(v);
 50                     in_que[v] = true;
 51                 }
 52             }
 53         }
 54     }
 55     if (pre[sink] == 0) {
 56         return false;
 57     }
 58     return true;
 59 }
 60 
 61 // fisrt : total cost 
 62 // srcond : min flow
 63 int mcmf(int src, int sink)
 64 {
 65     int res = INF;
 66     int pass_per_second = 0;
 67     int now_time = 0;
 68     int last_time = 0;
 69     while (spfa(src, sink) == true) {
 70         int min_flow = INF;
 71         for (int i = pre[sink]; i; i = pre[edge[i].u]) {
 72             // find the min flow in augmenting path
 73             min_flow = std::min(min_flow, edge[i].cap);
 74         }
 75         for (int i = pre[sink]; i; i = pre[edge[i].u]) {
 76             // update the cap in augmenting path
 77             edge[i].cap -= min_flow;
 78             edge[i^1].cap += min_flow;
 79             // printf("u = %d, v = %d, cost = %d, min_flow = %d
", edge[i].u, edge[i].v, edge[i].cost, min_flow);
 80             //min_cost += edge[i].cost * min_flow;
 81         }    
 82         k -= ( (dist[sink] -last_time)*pass_per_second + min_flow );
 83         last_time = dist[sink];
 84         pass_per_second += min_flow;
 85         int tmp = k;
 86         int ttt = last_time + ( (int)ceil(1.0*tmp/(pass_per_second) ));
 87         res = std::min(res, ttt);
 88         //printf("ttt = %d
", ttt);
 89         //printf("min_flow = %d, last_time = %d, pass_per_second = %d, k = %d
", min_flow, last_time, pass_per_second, k);
 90         if (k <= 0) {
 91             break;
 92         }
 93         
 94     }
 95 
 96     return res;
 97 }
 98 
 99 void addEdge(int u, int v, int cap, int cost)
100 {
101     edge[++tot] = Edge(u, v, cap, cost, head[u]);
102     head[u] = tot;
103 }
104 
105 void init()
106 {
107     tot = 1;
108     memset(head, 0, sizeof head);
109 }
110 
111 int main()
112 {
113     while (~scanf("%d%d%d", &n, &m, &k)) {
114         init();
115         for (int i = 1, u, v, cap, cost; i <= m; ++ i) {
116             // cost is the cost per flow in this edge
117             scanf("%d%d%d", &u, &v, &cap);
118             addEdge(u+1, v+1, cap, 1);
119             addEdge(v+1, u+1, 0, -1);
120         }
121         if (k == 0) {
122             puts("0");
123             continue;
124         }
125         int res = mcmf(1, n);
126         if (res == INF) {
127             puts("No solution");
128         }
129         else {
130             printf("%d
", res);
131         }
132     }
133     return 0;
134 }

View Code