Index: SRM/491/1C.cpp ================================================================== --- SRM/491/1C.cpp +++ SRM/491/1C.cpp @@ -60,55 +60,61 @@ static const Cost COST_INF = 1e+300; // !!EDIT HERE!! static const Flow FLOW_INF = 0x7fffffff; Cost total_cost = 0; Flow total_flow = 0; - vector h(N, 0); // potential - for(Flow RF=FLOW_INF; RF>0; ) // residual flow + vector dist(N, 0); // Distance from S : initially unknown. + for(;;) { - // Dijkstra -- find the min-cost path - vector d(N, COST_INF); d[S] = 0; + // Dijkstra : find the "shortest path" from S to T wrt C[][]. + // C[][] can be <0 so we must be careful. Instead of computing the shortest path directly, + // we compute the increase ("delta") from the shortest path in the previous iteration. + // Since shortest path cannot decrease, delta is always >=0 when traversing edges. + // Smallest delta implies smallest dist[T]+delta[T]. + vector delta(N, COST_INF); delta[S] = 0; vector prev(N, -1); - typedef pair< Cost, pair > cedge; + typedef pair< Cost, pair > cedge; priority_queue< cedge, vector, greater > Q; - Q.push( cedge(0, make_pair(S,S)) ); + Q.push( cedge(0, make_pair(S, S)) ); while( !Q.empty() ) { - cedge e = Q.top(); Q.pop(); - if( prev[e.second.second] >= 0 ) + const cedge e = Q.top(); Q.pop(); + const int u_prev = e.second.first; + const int u = e.second.second; + if( prev[u] >= 0 ) // visited continue; - prev[e.second.second] = e.second.first; + prev[u] = u_prev; - int u = e.second.second; for(int i=0; i 0 && d[v] > d[u]+r_cost ) - Q.push( cedge(d[v]=d[u]+r_cost, make_pair(u,v)) ); + const int v = G[u][i]; + const Cost v_delta = dist[u]+delta[u]+C[u][v] - dist[v]; + if( F[u][v]>0 && delta[v]>v_delta ) + Q.push( cedge(delta[v]=v_delta, make_pair(u,v)) ); } } + // If T is unreachable, finished. if( prev[T] < 0 ) - break; // Finished + break; + + // Update the distance table. + for(int u=0; u pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_)); int k = 50; double _ = 16.846938775510203; END -/* CASE(5) - double pileA_[] = ; + 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}; vector pileA(pileA_, pileA_+sizeof(pileA_)/sizeof(*pileA_)); - double pileB_[] = ; + 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}; vector pileB(pileB_, pileB_+sizeof(pileB_)/sizeof(*pileB_)); - int k = ; - double _ = ; + int k = 50; + double _ = 21.128144186967717; END -*/ } // END CUT HERE + Index: lib/graph/mincostFlow.cpp ================================================================== --- lib/graph/mincostFlow.cpp +++ lib/graph/mincostFlow.cpp @@ -1,13 +1,14 @@ //------------------------------------------------------------- // MinCost-MaxFlow -// O(??) +// O(F E log E) // F:flow +// See http://d.hatena.ne.jp/tsukuno/20120320#1332179143 // // Verified by -// - SRM 487 Div2 LV3 +// - (SRM 487 Div2 LV3) in previous version +// - (SRM 526 Div1 LV1) in previous version // - SRM 491 Div1 LV3 -// - SRM 526 Div1 LV1 //------------------------------------------------------------- #include #include #include @@ -51,59 +52,65 @@ } pair calc( Vert s_, Vert t_ ) { const int N=idgen.size(), S=idgen.v2id(s_), T=idgen.v2id(t_); - static const Cost COST_INF = // 0x7fffffff; // !!EDIT HERE!! - static const Flow FLOW_INF = // 0x7fffffff; + static const Cost COST_INF = 1e+300; // !!EDIT HERE!! + static const Flow FLOW_INF = 0x7fffffff; Cost total_cost = 0; Flow total_flow = 0; - vector h(N, 0); // potential - for(Flow RF=FLOW_INF; RF>0; ) // residual flow + vector dist(N, 0); // Distance from S : initially unknown. + for(;;) { - // Dijkstra -- find the min-cost path - vector d(N, COST_INF); d[S] = 0; + // Dijkstra : find the "shortest path" from S to T wrt C[][]. + // C[][] can be <0 so we must be careful. Instead of computing the shortest path directly, + // we compute the increase ("delta") from the shortest path in the previous iteration. + // Since shortest path cannot decrease, delta is always >=0 when traversing edges. + // Smallest delta implies smallest dist[T]+delta[T]. + vector delta(N, COST_INF); delta[S] = 0; vector prev(N, -1); - typedef pair< Cost, pair > cedge; + typedef pair< Cost, pair > cedge; priority_queue< cedge, vector, greater > Q; - Q.push( cedge(0, make_pair(S,S)) ); + Q.push( cedge(0, make_pair(S, S)) ); while( !Q.empty() ) { - cedge e = Q.top(); Q.pop(); - if( prev[e.second.second] >= 0 ) + const cedge e = Q.top(); Q.pop(); + const int u_prev = e.second.first; + const int u = e.second.second; + if( prev[u] >= 0 ) // visited continue; - prev[e.second.second] = e.second.first; + prev[u] = u_prev; - int u = e.second.second; for(int i=0; i 0 && d[v] > d[u]+r_cost ) - Q.push( cedge(d[v]=d[u]+r_cost, make_pair(u,v)) ); + const int v = G[u][i]; + const Cost v_delta = dist[u]+delta[u]+C[u][v] - dist[v]; + if( F[u][v]>0 && delta[v]>v_delta ) + Q.push( cedge(delta[v]=v_delta, make_pair(u,v)) ); } } + // If T is unreachable, finished. if( prev[T] < 0 ) - break; // Finished + break; + + // Update the distance table. + for(int u=0; u