Differences From Artifact [4236b55037662c66]:
- File
lib/graph/mincostFlow.cpp
- 2011-12-17 16:43:26 - part of checkin [f6764c7ea7] on branch trunk - 526 (user: kinaba) [annotate]
To Artifact [f4ac9260460b2241]:
- File
lib/graph/mincostFlow.cpp
- 2012-04-03 13:55:54 - part of checkin [524cc07867] on branch trunk - Updated min cost flow library reading tsukuno's diary. (user: kinaba) [annotate]
1 1 //-------------------------------------------------------------
2 2 // MinCost-MaxFlow
3 -// O(??)
3 +// O(F E log E) // F:flow
4 +// See http://d.hatena.ne.jp/tsukuno/20120320#1332179143
4 5 //
5 6 // Verified by
6 -// - SRM 487 Div2 LV3
7 +// - (SRM 487 Div2 LV3) in previous version
8 +// - (SRM 526 Div1 LV1) in previous version
7 9 // - SRM 491 Div1 LV3
8 -// - SRM 526 Div1 LV1
9 10 //-------------------------------------------------------------
10 11
11 12 #include <iostream>
12 13 #include <string>
13 14 #include <vector>
14 15 #include <map>
15 16 #include <queue>
................................................................................
49 50 F[s][t] = f;
50 51 F[t][s] = 0;
51 52 }
52 53
53 54 pair<Cost, Flow> calc( Vert s_, Vert t_ )
54 55 {
55 56 const int N=idgen.size(), S=idgen.v2id(s_), T=idgen.v2id(t_);
56 - static const Cost COST_INF = // 0x7fffffff; // !!EDIT HERE!!
57 - static const Flow FLOW_INF = // 0x7fffffff;
57 + static const Cost COST_INF = 1e+300; // !!EDIT HERE!!
58 + static const Flow FLOW_INF = 0x7fffffff;
58 59
59 60 Cost total_cost = 0;
60 61 Flow total_flow = 0;
61 - vector<Cost> h(N, 0); // potential
62 - for(Flow RF=FLOW_INF; RF>0; ) // residual flow
62 + vector<Cost> dist(N, 0); // Distance from S : initially unknown.
63 + for(;;)
63 64 {
64 - // Dijkstra -- find the min-cost path
65 - vector<Cost> d(N, COST_INF); d[S] = 0;
65 + // Dijkstra : find the "shortest path" from S to T wrt C[][].
66 + // C[][] can be <0 so we must be careful. Instead of computing the shortest path directly,
67 + // we compute the increase ("delta") from the shortest path in the previous iteration.
68 + // Since shortest path cannot decrease, delta is always >=0 when traversing edges.
69 + // Smallest delta implies smallest dist[T]+delta[T].
70 + vector<Cost> delta(N, COST_INF); delta[S] = 0;
66 71 vector<int> prev(N, -1);
67 72
68 - typedef pair< Cost, pair<int,int> > cedge;
73 + typedef pair< Cost, pair<int, int> > cedge;
69 74 priority_queue< cedge, vector<cedge>, greater<cedge> > Q;
70 - Q.push( cedge(0, make_pair(S,S)) );
75 + Q.push( cedge(0, make_pair(S, S)) );
71 76 while( !Q.empty() ) {
72 - cedge e = Q.top(); Q.pop();
73 - if( prev[e.second.second] >= 0 )
77 + const cedge e = Q.top(); Q.pop();
78 + const int u_prev = e.second.first;
79 + const int u = e.second.second;
80 + if( prev[u] >= 0 ) // visited
74 81 continue;
75 - prev[e.second.second] = e.second.first;
82 + prev[u] = u_prev;
76 83
77 - int u = e.second.second;
78 84 for(int i=0; i<G[u].size(); ++i) {
79 - int v = G[u][i];
80 - Cost r_cost = C[u][v] + h[u] - h[v];
81 - if( F[u][v] > 0 && d[v] > d[u]+r_cost )
82 - Q.push( cedge(d[v]=d[u]+r_cost, make_pair(u,v)) );
85 + const int v = G[u][i];
86 + const Cost v_delta = dist[u]+delta[u]+C[u][v] - dist[v];
87 + if( F[u][v]>0 && delta[v]>v_delta )
88 + Q.push( cedge(delta[v]=v_delta, make_pair(u,v)) );
83 89 }
84 90 }
85 91
92 + // If T is unreachable, finished.
86 93 if( prev[T] < 0 )
87 - break; // Finished
94 + break;
95 +
96 + // Update the distance table.
97 + for(int u=0; u<N; ++u)
98 + if( delta[u] != COST_INF )
99 + dist[u] += delta[u];
88 100
89 - // Run the flow as much as possible
90 - Flow f = RF;
101 + // How much water can flow on the min-cost path?
102 + Flow f = FLOW_INF;
91 103 for(int u=T; u!=S; u=prev[u])
92 104 f = min(f, F[prev[u]][u]);
93 - RF -= f;
94 - total_flow += f;
95 105
96 - for(int u=T; u!=S; u=prev[u])
97 - {
106 + // Run the flow as much as possible
107 + total_flow += f;
108 + for(int u=T; u!=S; u=prev[u]) {
98 109 total_cost += f * C[prev[u]][u];
99 110 F[prev[u]][u] -= f;
100 111 F[u][prev[u]] += f;
101 112 }
102 -
103 - // Update the potential
104 - for(int u=0; u<N; ++u)
105 - h[u] += d[u];
106 113 }
107 114 return make_pair(total_cost, total_flow);
108 115 }
109 116 };