1 //------------------------------------------------------------- 1 //------------------------------------------------------------- 2 // MinCost-MaxFlow 2 // MinCost-MaxFlow 3 // O(??) 3 // O(??) 4 // 4 // 5 // Verified by 5 // Verified by 6 // - SRM 487 Div2 LV3 6 // - SRM 487 Div2 LV3 7 // - SRM 491 Div1 LV3 7 // - SRM 491 Div1 LV3 > 8 // - SRM 526 Div1 LV1 8 //------------------------------------------------------------- 9 //------------------------------------------------------------- 9 10 10 #include <iostream> 11 #include <iostream> 11 #include <string> 12 #include <string> 12 #include <vector> 13 #include <vector> 13 #include <map> 14 #include <map> 14 #include <queue> 15 #include <queue> ................................................................................................................................................................................ 48 F[s][t] = f; 49 F[s][t] = f; 49 F[t][s] = 0; 50 F[t][s] = 0; 50 } 51 } 51 52 52 pair<Cost, Flow> calc( Vert s_, Vert t_ ) 53 pair<Cost, Flow> calc( Vert s_, Vert t_ ) 53 { 54 { 54 const int N=idgen.size(), S=idgen.v2id(s_), T=idgen.v2id(t_); 55 const int N=idgen.size(), S=idgen.v2id(s_), T=idgen.v2id(t_); 55 static const Cost COST_INF = 1e+300; // !!EDIT HERE!! | 56 static const Cost COST_INF = // 0x7fffffff; // !!EDIT HERE!! 56 static const Flow FLOW_INF = 0x7fffffff; | 57 static const Flow FLOW_INF = // 0x7fffffff; 57 58 58 Cost total_cost = 0; 59 Cost total_cost = 0; 59 Flow total_flow = 0; 60 Flow total_flow = 0; 60 vector<Cost> h(N, 0); // potential 61 vector<Cost> h(N, 0); // potential 61 for(Flow RF=FLOW_INF; RF>0; ) // residual flow 62 for(Flow RF=FLOW_INF; RF>0; ) // residual flow 62 { 63 { 63 // Dijkstra -- find the min-cost path 64 // Dijkstra -- find the min-cost path