Differences From Artifact [a86509e21e3c5ec5]:
- File
_lib/graph/mincostFlow.cpp
- 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]
- File
lib/graph/mincostFlow.cpp
- 2011-02-23 11:18:09 - part of checkin [23dfcca431] on branch trunk - renamed _lib to lib (user: kinaba) [annotate]
To Artifact [4236b55037662c66]:
- File
lib/graph/mincostFlow.cpp
- 2011-12-17 16:43:26 - part of checkin [f6764c7ea7] on branch trunk - 526 (user: kinaba) [annotate]
1 1 //-------------------------------------------------------------
2 2 // MinCost-MaxFlow
3 3 // O(??)
4 4 //
5 5 // Verified by
6 6 // - SRM 487 Div2 LV3
7 7 // - SRM 491 Div1 LV3
8 +// - SRM 526 Div1 LV1
8 9 //-------------------------------------------------------------
9 10
10 11 #include <iostream>
11 12 #include <string>
12 13 #include <vector>
13 14 #include <map>
14 15 #include <queue>
................................................................................
48 49 F[s][t] = f;
49 50 F[t][s] = 0;
50 51 }
51 52
52 53 pair<Cost, Flow> calc( Vert s_, Vert t_ )
53 54 {
54 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 Flow FLOW_INF = 0x7fffffff;
56 + static const Cost COST_INF = // 0x7fffffff; // !!EDIT HERE!!
57 + static const Flow FLOW_INF = // 0x7fffffff;
57 58
58 59 Cost total_cost = 0;
59 60 Flow total_flow = 0;
60 61 vector<Cost> h(N, 0); // potential
61 62 for(Flow RF=FLOW_INF; RF>0; ) // residual flow
62 63 {
63 64 // Dijkstra -- find the min-cost path