MinCostFlow
It solves Minimum-cost flow problem.
Constructor
mcf_graph<Cap, Cost> graph(int n);
It creates a directed graph with $n$ vertices and $0$ edges. Cap and Cost are the type of the capacity and the cost, respectively.
Constraints
- $0 \leq n \leq 10^8$
Cap and Cost are int or ll.
Complexity
add_edge
int graph.add_edge(int from, int to, Cap cap, Cost cost);
It adds an edge oriented from from to to with capacity cap and cost cost. It returns an integer $k$ such that this is the $k$-th edge that is added.
Constraints
- $0 \leq \mathrm{from}, \mathrm{to} \lt n$
- $0 \leq \mathrm{cap}, \mathrm{cost}$
Complexity
min_cost_max_flow
(1) pair<Cap, Cost> graph.flow(int s, int t);
(2) pair<Cap, Cost> graph.flow(int s, int t, Cap flow_limit);
- It augments the flow from $s$ to $t$ as much as possible. It returns the amount of the flow and the cost.
- (1) It augments the $s-t$ flow as much as possible.
- (2) It augments the $s-t$ flow as much as possible, until reaching the amount of
flow_limit.
Constraints
Complexity
min_cost_slope
vector<pair<Cap, Cost>> graph.slope(int s, int t);
vector<pair<Cap, Cost>> graph.slope(int s, int t, Cap flow_limit);
Let $g$ be a function such that $g(x)$ is the cost of the minimum cost $s-t$ flow when the amount of the flow is exactly $x$. $g$ is known to be piecewise linear.
It returns $g$ as the list of the changepoints, that satisfies the followings.
- The first element of the list is $(0, 0)$.
- Both of
.first and .second are strictly increasing.
- No three changepoints are on the same line.
- (1) The last element of the list is $(x, g(x))$, where $x$ is the maximum amount of the $s-t$ flow.
- (2) The last element of the list is $(y, g(y))$, where $y = \min(x, \mathrm{flow\_limit})$.
Constraints
Let $x$ be the maximum cost among all edges.
- $s \neq t$
- You can't call
min_cost_slope or min_cost_max_flow multiple times.
- The total amount of the flow is in
Cap.
- The total cost of the flow is in
Cost.
- (Cost :
int): $0 \leq nx \leq 2 \times 10^9 + 1000$
- (Cost :
ll): $0 \leq nx \leq 8 \times 10^{18} + 1000$
Complexity
- $O(F (n + m) \log (n + m))$, where $F$ is the amount of the flow and $m$ is the number of added edges.
edges
struct edge<Cap, Cost> {
int from, to;
Cap cap, flow;
Cost cost;
};
(1) mcf_graph<Cap, Cost>::edge graph.get_edge(int i);
(2) vector<mcf_graph<Cap, Cost>::edge> graph.edges();
- It returns the current internal state of the edges.
- The edges are ordered in the same order as added by
add_edge.
Constraints
Complexity
- (1): $O(1)$
- (2): $O(m)$, where $m$ is the number of added edges.
Examples
#include <atcoder/mincostflow>
#include <iostream>
using namespace std;
using namespace atcoder;
const long long BIG = 1'000'000'000;
int main() {
int n, k;
cin >> n >> k;
/**
* generate (s -> row -> column -> t) graph
* i-th row correspond to vertex i
* i-th col correspond to vertex n + i
**/
mcf_graph<int, long long> g(2 * n + 2);
int s = 2 * n, t = 2 * n + 1;
// we can "waste" the flow
g.add_edge(s, t, n * k, BIG);
for (int i = 0; i < n; i++) {
g.add_edge(s, i, k, 0);
g.add_edge(n + i, t, k, 0);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
long long a;
cin >> a;
g.add_edge(i, n + j, 1, BIG - a);
}
}
auto result = g.flow(s, t, n * k);
cout << 1LL * n * k * BIG - result.second << endl;
vector<string> grid(n, string(n, '.'));
auto edges = g.edges();
for (auto e : edges) {
if (e.from == s || e.to == t || e.flow == 0) continue;
grid[e.from][e.to - n] = 'X';
}
for (int i = 0; i < n; i++) {
cout << grid[i] << endl;
}
return 0;
}