1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
typedef ll COST_T;
typedef ll CAP_T;
constexpr COST_T COST_INF = 0x3f3f3f3f3f3f3f3fll;
constexpr CAP_T CAP_INF = 0x3f3f3f3f3f3f3f3fll;
class MinCostMaxFlow {
struct Edge{
int from, to;
CAP_T flow, cap;
COST_T cost;
};
int n;
CAP_T maxFlow;
COST_T minCost;
vector<vector<int>> g;
CAP_T* a = NULL;
COST_T* d = NULL;
vector<Edge> edges;
bool* vis = NULL;
int* p = NULL;
public:
MinCostMaxFlow(int n): n(n), g(n, vector<int>()), a(new CAP_T[n]), d(new COST_T[n]), vis(new bool[n]), p(new int[n]) {
}
~MinCostMaxFlow() {
delete [] a;
delete [] d;
delete [] vis;
delete [] p;
}
void add_edge(int from, int to, CAP_T cap, COST_T cost) {
Edge temp1 = { from, to, 0, cap, cost };
Edge temp2 = { to, from, 0, 0, -cost };
edges.push_back(temp1);
edges.push_back(temp2);
int len = edges.size();
g[from].push_back(len - 2);
g[to].push_back(len - 1);
}
bool bellmanford(int s, int t) {
fill(d, d+n, COST_INF);
d[s] = 0;
memset(vis, 0, sizeof(*vis)*n);
memset(p, -1, sizeof(*p)*n);
p[s] = -1;
a[s] = CAP_INF;
queue<int> Q;
Q.push(s);
vis[s] = true;
while (!Q.empty()) {
int u = Q.front();
Q.pop();
vis[u] = false;
for (int i = 0; i < g[u].size(); i++) {
Edge& e = edges[g[u][i]];
if (e.cap > e.flow && d[e.to] > d[u] + e.cost) {
d[e.to] = d[u] + e.cost;
p[e.to] = g[u][i];
a[e.to] = min(a[u], e.cap - e.flow);
if (!vis[e.to]) {
Q.push(e.to);
vis[e.to] = true;
}
}
}
}
if (d[t] == COST_INF) return false;
maxFlow += a[t];
minCost += d[t] * a[t];
for (int i = t; i != s; i = edges[p[i]].from) {
edges[p[i]].flow += a[t];
edges[p[i] ^ 1].flow -= a[t];
}
return true;
}
pair<COST_T, CAP_T> solve(int s, int t) {
memset(a, 0, sizeof(*a)*n);
maxFlow = 0;
minCost = 0;
while (bellmanford(s, t))
continue;
return make_pair(minCost, maxFlow);
}
};
|