It solves maximum flow problem.
mf_graph<Cap> graph(int n)
It creates a graph of n
vertices and edges. Cap
is the type of the capacity.
Constraints
Cap
is int
or ll
Complexity
int graph.add_edge(int from, int to, Cap cap);
It adds an edge oriented from the vertex from
to the vertex to
with the capacity cap
and the flow amount . It returns an integer such that this is the -th edge that is added.
Constraints
Complexity
(1) Cap graph.flow(int s, int t);
(2) Cap graph.flow(int s, int t, Cap flow_limit);
Constraints
Cap
.Complexity
where is the number of added edges.
vector<bool> graph.min_cut(int s)
It returns a vector of length , such that the -th element is true
if and only if there is a directed path from to in the residual network.
The returned vector corresponds to a minimum cut after calling flow(s, t)
exactly once without flow_limit
. See Appendix for further details.
Complexity
struct mf_graph<Cap>::edge {
int from, to;
Cap cap, flow;
};
(1) mf_graph<Cap>::edge graph.get_edge(int i);
(2) vector<mf_graph<Cap>::edge> graph.edges();
add_edge
.Constraints
Complexity
void graph.change_edge(int i, Cap new_cap, Cap new_flow);
It changes the capacity and the flow amount of the -th edge to new_cap
and new_flow
, respectively. It doesn't change the capacity or the flow amount of other edges. See Appendix for further details.
Constraints
Complexity