Overview
| SHA1 Hash: | 524cc078671bf4c92d4c78dca08e702bf424904a |
|---|---|
| Date: | 2012-04-03 13:55:54 |
| User: | kinaba |
| Comment: | Updated min cost flow library reading tsukuno's diary. |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Modified SRM/491/1C.cpp from [fc13d82ca1ace550] to [4e3a76b4d8344d4d].
58 58 { 59 59 const int N=idgen.size(), S=idgen.v2id(s_), T=idgen.v2id(t_); 60 60 static const Cost COST_INF = 1e+300; // !!EDIT HERE!! 61 61 static const Flow FLOW_INF = 0x7fffffff; 62 62 63 63 Cost total_cost = 0; 64 64 Flow total_flow = 0; 65 - vector<Cost> h(N, 0); // potential 66 - for(Flow RF=FLOW_INF; RF>0; ) // residual flow 65 + vector<Cost> dist(N, 0); // Distance from S : initially unknown. 66 + for(;;) 67 67 { 68 - // Dijkstra -- find the min-cost path 69 - vector<Cost> d(N, COST_INF); d[S] = 0; 68 + // Dijkstra : find the "shortest path" from S to T wrt C[][]. 69 + // C[][] can be <0 so we must be careful. Instead of computing the shortest path directly, 70 + // we compute the increase ("delta") from the shortest path in the previous iteration. 71 + // Since shortest path cannot decrease, delta is always >=0 when traversing edges. 72 + // Smallest delta implies smallest dist[T]+delta[T]. 73 + vector<Cost> delta(N, COST_INF); delta[S] = 0; 70 74 vector<int> prev(N, -1); 71 75 72 - typedef pair< Cost, pair<int,int> > cedge; 76 + typedef pair< Cost, pair<int, int> > cedge; 73 77 priority_queue< cedge, vector<cedge>, greater<cedge> > Q; 74 - Q.push( cedge(0, make_pair(S,S)) ); 78 + Q.push( cedge(0, make_pair(S, S)) ); 75 79 while( !Q.empty() ) { 76 - cedge e = Q.top(); Q.pop(); 77 - if( prev[e.second.second] >= 0 ) 80 + const cedge e = Q.top(); Q.pop(); 81 + const int u_prev = e.second.first; 82 + const int u = e.second.second; 83 + if( prev[u] >= 0 ) // visited 78 84 continue; 79 - prev[e.second.second] = e.second.first; 85 + prev[u] = u_prev; 80 86 81 - int u = e.second.second; 82 87 for(int i=0; i<G[u].size(); ++i) { 83 - int v = G[u][i]; 84 - Cost r_cost = C[u][v] + h[u] - h[v]; 85 - if( F[u][v] > 0 && d[v] > d[u]+r_cost ) 86 - Q.push( cedge(d[v]=d[u]+r_cost, make_pair(u,v)) ); 88 + const int v = G[u][i]; 89 + const Cost v_delta = dist[u]+delta[u]+C[u][v] - dist[v]; 90 + if( F[u][v]>0 && delta[v]>v_delta ) 91 + Q.push( cedge(delta[v]=v_delta, make_pair(u,v)) ); 87 92 } 88 93 } 89 94 95 + // If T is unreachable, finished. 90 96 if( prev[T] < 0 ) 91 - break; // Finished 97 + break; 98 + 99 + // Update the distance table. 100 + for(int u=0; u<N; ++u) 101 + if( delta[u] != COST_INF ) 102 + dist[u] += delta[u]; 92 103 93 - // Run the flow as much as possible 94 - Flow f = RF; 104 + // How much water can flow on the min-cost path? 105 + Flow f = FLOW_INF; 95 106 for(int u=T; u!=S; u=prev[u]) 96 107 f = min(f, F[prev[u]][u]); 97 - RF -= f; 98 - total_flow += f; 99 108 100 - for(int u=T; u!=S; u=prev[u]) 101 - { 109 + // Run the flow as much as possible 110 + total_flow += f; 111 + for(int u=T; u!=S; u=prev[u]) { 102 112 total_cost += f * C[prev[u]][u]; 103 113 F[prev[u]][u] -= f; 104 114 F[u][prev[u]] += f; 105 115 } 106 - 107 - // Update the potential 108 - for(int u=0; u<N; ++u) 109 - h[u] += d[u]; 110 116 } 111 117 return make_pair(total_cost, total_flow); 112 118 } 113 119 }; 114 120 115 121 class FoxCardGame { public: 116 122 double theMaxProportion(vector <double> pileA, vector <double> pileB, int k) ................................................................................ 195 201 double pileA_[] = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0, 17.0, 18.0, 19.0, 20.0, 21.0, 22.0, 23.0, 24.0, 25.0, 26.0, 27.0, 28.0, 29.0, 30.0, 31.0, 32.0, 33.0, 34.0, 35.0, 36.0, 37.0, 38.0, 39.0, 40.0, 41.0, 42.0, 43.0, 44.0, 45.0, 46.0, 47.0, 48.0, 49.0, 50.0}; 196 202 vector <double> pileA(pileA_, pileA_+sizeof(pileA_)/sizeof(*pileA_)); 197 203 double pileB_[] = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0, 17.0, 18.0, 19.0, 20.0, 21.0, 22.0, 23.0, 24.0, 25.0, 26.0, 27.0, 28.0, 29.0, 30.0, 31.0, 32.0, 33.0, 34.0, 35.0, 36.0, 37.0, 38.0, 39.0, 40.0, 41.0, 42.0, 43.0, 44.0, 45.0, 46.0, 47.0, 48.0, 49.0, 50.0}; 198 204 vector <double> pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_)); 199 205 int k = 50; 200 206 double _ = 16.846938775510203; 201 207 END 202 -/* 203 208 CASE(5) 204 - double pileA_[] = ; 209 + double pileA_[] = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0, 17.0, 18.0, 19.0, 20.0, 21.0, 22.0, 23.0, 24.0, 25.0, 26.0, 27.0, 28.0, 29.0, 30.0, 31.0, 32.0, 33.0, 34.0, 35.0, 36.0, 37.0, 38.0, 39.0, 40.0, 41.0, 42.0, 43.0, 44.0, 45.0, 46.0, 47.0, 48.0, 49.0, 50.0}; 205 210 vector <double> pileA(pileA_, pileA_+sizeof(pileA_)/sizeof(*pileA_)); 206 - double pileB_[] = ; 211 + double pileB_[] = {51.0, 52.0, 53.0, 54.0, 55.0, 56.0, 57.0, 58.0, 59.0, 60.0, 61.0, 62.0, 63.0, 64.0, 65.0, 66.0, 67.0, 68.0, 69.0, 70.0, 71.0, 72.0, 73.0, 74.0, 75.0, 76.0, 77.0, 78.0, 79.0, 80.0, 81.0, 82.0, 83.0, 84.0, 85.0, 86.0, 87.0, 88.0, 89.0, 90.0, 91.0, 92.0, 93.0, 94.0, 95.0, 96.0, 97.0, 98.0, 99.0, 100.0}; 207 212 vector <double> pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_)); 208 - int k = ; 209 - double _ = ; 213 + int k = 50; 214 + double _ = 21.128144186967717; 210 215 END 211 -*/ 212 216 } 213 217 // END CUT HERE 218 +
Modified lib/graph/mincostFlow.cpp from [4236b55037662c66] to [f4ac9260460b2241].
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 };