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 const int N=idgen.size(), S=idgen.v2id(s_), T=idgen.v2id(t_); 59 const int N=idgen.size(), S=idgen.v2id(s_), T=idgen.v2id(t_); 60 static const Cost COST_INF = 1e+300; // !!EDIT HERE!! 60 static const Cost COST_INF = 1e+300; // !!EDIT HERE!! 61 static const Flow FLOW_INF = 0x7fffffff; 61 static const Flow FLOW_INF = 0x7fffffff; 62 62 63 Cost total_cost = 0; 63 Cost total_cost = 0; 64 Flow total_flow = 0; 64 Flow total_flow = 0; 65 vector<Cost> h(N, 0); // potential | 65 vector<Cost> dist(N, 0); // Distance from S : initially unknown. 66 for(Flow RF=FLOW_INF; RF>0; ) // residual flow | 66 for(;;) 67 { 67 { 68 // Dijkstra -- find the min-cost path | 68 // Dijkstra : find the "shortest path" from S to T wrt C > 69 // C[][] can be <0 so we must be careful. Instead of c > 70 // we compute the increase ("delta") from the shortest > 71 // Since shortest path cannot decrease, delta is alway > 72 // Smallest delta implies smallest dist[T]+delta[T]. 69 vector<Cost> d(N, COST_INF); d[S] = 0; | 73 vector<Cost> delta(N, COST_INF); delta[S] = 0; 70 vector<int> prev(N, -1); 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 priority_queue< cedge, vector<cedge>, greater<cedge> > Q 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 while( !Q.empty() ) { 79 while( !Q.empty() ) { 76 cedge e = Q.top(); Q.pop(); | 80 const cedge e = Q.top(); Q.pop(); > 81 const int u_prev = e.second.first; 77 if( prev[e.second.second] >= 0 ) | 82 const int u = e.second.second; > 83 if( prev[u] >= 0 ) // visited 78 continue; 84 continue; 79 prev[e.second.second] = e.second.first; | 85 prev[u] = u_prev; 80 86 81 int u = e.second.second; < 82 for(int i=0; i<G[u].size(); ++i) { 87 for(int i=0; i<G[u].size(); ++i) { 83 int v = G[u][i]; | 88 const int v = G[u][i]; 84 Cost r_cost = C[u][v] + h[u] - h[v]; | 89 const Cost v_delta = dist[u]+delta[u]+C[ 85 if( F[u][v] > 0 && d[v] > d[u]+r_cost ) | 90 if( F[u][v]>0 && delta[v]>v_delta ) 86 Q.push( cedge(d[v]=d[u]+r_cost, | 91 Q.push( cedge(delta[v]=v_delta, 87 } 92 } 88 } 93 } 89 94 > 95 // If T is unreachable, finished. 90 if( prev[T] < 0 ) 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 | 104 // How much water can flow on the min-cost path? 94 Flow f = RF; | 105 Flow f = FLOW_INF; 95 for(int u=T; u!=S; u=prev[u]) 106 for(int u=T; u!=S; u=prev[u]) 96 f = min(f, F[prev[u]][u]); 107 f = min(f, F[prev[u]][u]); 97 RF -= f; < 98 total_flow += f; < 99 108 > 109 // Run the flow as much as possible > 110 total_flow += f; 100 for(int u=T; u!=S; u=prev[u]) | 111 for(int u=T; u!=S; u=prev[u]) { 101 { < 102 total_cost += f * C[prev[u]][u]; 112 total_cost += f * C[prev[u]][u]; 103 F[prev[u]][u] -= f; 113 F[prev[u]][u] -= f; 104 F[u][prev[u]] += f; 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 return make_pair(total_cost, total_flow); 117 return make_pair(total_cost, total_flow); 112 } 118 } 113 }; 119 }; 114 120 115 class FoxCardGame { public: 121 class FoxCardGame { public: 116 double theMaxProportion(vector <double> pileA, vector <double> pileB, in 122 double theMaxProportion(vector <double> pileA, vector <double> pileB, in ................................................................................................................................................................................ 195 double pileA_[] = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11 201 double pileA_[] = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11 196 vector <double> pileA(pileA_, pileA_+sizeof(pileA_)/sizeof(*pileA_)); 202 vector <double> pileA(pileA_, pileA_+sizeof(pileA_)/sizeof(*pileA_)); 197 double pileB_[] = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11 203 double pileB_[] = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11 198 vector <double> pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_)); 204 vector <double> pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_)); 199 int k = 50; 205 int k = 50; 200 double _ = 16.846938775510203; 206 double _ = 16.846938775510203; 201 END 207 END 202 /* < 203 CASE(5) 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 205 vector <double> pileA(pileA_, pileA_+sizeof(pileA_)/sizeof(*pileA_)); 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, 207 vector <double> pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_)); 212 vector <double> pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_)); 208 int k = ; | 213 int k = 50; 209 double _ = ; | 214 double _ = 21.128144186967717; 210 END 215 END 211 */ < 212 } 216 } 213 // END CUT HERE 217 // END CUT HERE > 218
Modified lib/graph/mincostFlow.cpp from [4236b55037662c66] to [f4ac9260460b2241].
1 //------------------------------------------------------------- 1 //------------------------------------------------------------- 2 // MinCost-MaxFlow 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 // Verified by 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 // - SRM 491 Div1 LV3 9 // - SRM 491 Div1 LV3 8 // - SRM 526 Div1 LV1 < 9 //------------------------------------------------------------- 10 //------------------------------------------------------------- 10 11 11 #include <iostream> 12 #include <iostream> 12 #include <string> 13 #include <string> 13 #include <vector> 14 #include <vector> 14 #include <map> 15 #include <map> 15 #include <queue> 16 #include <queue> ................................................................................................................................................................................ 49 F[s][t] = f; 50 F[s][t] = f; 50 F[t][s] = 0; 51 F[t][s] = 0; 51 } 52 } 52 53 53 pair<Cost, Flow> calc( Vert s_, Vert t_ ) 54 pair<Cost, Flow> calc( Vert s_, Vert t_ ) 54 { 55 { 55 const int N=idgen.size(), S=idgen.v2id(s_), T=idgen.v2id(t_); 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 Cost COST_INF = 1e+300; // !!EDIT HERE!! 57 static const Flow FLOW_INF = // 0x7fffffff; | 58 static const Flow FLOW_INF = 0x7fffffff; 58 59 59 Cost total_cost = 0; 60 Cost total_cost = 0; 60 Flow total_flow = 0; 61 Flow total_flow = 0; 61 vector<Cost> h(N, 0); // potential | 62 vector<Cost> dist(N, 0); // Distance from S : initially unknown. 62 for(Flow RF=FLOW_INF; RF>0; ) // residual flow | 63 for(;;) 63 { 64 { 64 // Dijkstra -- find the min-cost path | 65 // Dijkstra : find the "shortest path" from S to T wrt C > 66 // C[][] can be <0 so we must be careful. Instead of c > 67 // we compute the increase ("delta") from the shortest > 68 // Since shortest path cannot decrease, delta is alway > 69 // Smallest delta implies smallest dist[T]+delta[T]. 65 vector<Cost> d(N, COST_INF); d[S] = 0; | 70 vector<Cost> delta(N, COST_INF); delta[S] = 0; 66 vector<int> prev(N, -1); 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 priority_queue< cedge, vector<cedge>, greater<cedge> > Q 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 while( !Q.empty() ) { 76 while( !Q.empty() ) { 72 cedge e = Q.top(); Q.pop(); | 77 const cedge e = Q.top(); Q.pop(); > 78 const int u_prev = e.second.first; 73 if( prev[e.second.second] >= 0 ) | 79 const int u = e.second.second; > 80 if( prev[u] >= 0 ) // visited 74 continue; 81 continue; 75 prev[e.second.second] = e.second.first; | 82 prev[u] = u_prev; 76 83 77 int u = e.second.second; < 78 for(int i=0; i<G[u].size(); ++i) { 84 for(int i=0; i<G[u].size(); ++i) { 79 int v = G[u][i]; | 85 const int v = G[u][i]; 80 Cost r_cost = C[u][v] + h[u] - h[v]; | 86 const Cost v_delta = dist[u]+delta[u]+C[ 81 if( F[u][v] > 0 && d[v] > d[u]+r_cost ) | 87 if( F[u][v]>0 && delta[v]>v_delta ) 82 Q.push( cedge(d[v]=d[u]+r_cost, | 88 Q.push( cedge(delta[v]=v_delta, 83 } 89 } 84 } 90 } 85 91 > 92 // If T is unreachable, finished. 86 if( prev[T] < 0 ) 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 | 101 // How much water can flow on the min-cost path? 90 Flow f = RF; | 102 Flow f = FLOW_INF; 91 for(int u=T; u!=S; u=prev[u]) 103 for(int u=T; u!=S; u=prev[u]) 92 f = min(f, F[prev[u]][u]); 104 f = min(f, F[prev[u]][u]); 93 RF -= f; < 94 total_flow += f; < 95 105 > 106 // Run the flow as much as possible > 107 total_flow += f; 96 for(int u=T; u!=S; u=prev[u]) | 108 for(int u=T; u!=S; u=prev[u]) { 97 { < 98 total_cost += f * C[prev[u]][u]; 109 total_cost += f * C[prev[u]][u]; 99 F[prev[u]][u] -= f; 110 F[prev[u]][u] -= f; 100 F[u][prev[u]] += f; 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 return make_pair(total_cost, total_flow); 114 return make_pair(total_cost, total_flow); 108 } 115 } 109 }; 116 };