[AHOI2009] 最小割
首先考虑如何处理可行边，对于边 \(\left(u, v\right)\)，其为可行边与同时满足下列两个条件互为充要条件：
- \(c_f(u, v) = 0\)
- 在 \(G_f\) 中不存在路径 \(u \rightarrow v\)
首先可以发现若存在 \(G_f\) 使得 \(c_f(u, v) > 0\)，那么一定不会割这条边。
若 \(G_f\) 中存在路径 \(u \rightarrow v\)，那么可以通过将边 \(\left(u, v\right)\) 的一小部分流量通过 \(G_f\) 中存在路径 \(u \rightarrow v\) 传递。这样之后有 \(c_f(u, v) > 0\)，那么一定不会割这条边。
考虑在可行边的基础上添加什么条件才可以使得边为必须边。
可以发现，若对于可行边 \(\left(u, v\right)\)，若在 \(G_f\) 上不存在路径使得 \(S \rightarrow u\)，那么在 \(G\) 的任意一条路径 \(S \rightarrow u\) 上，均存在令一条可行边，因此边 \(\left(u, v\right)\) 不是必须边。
所以可行边 \(\left(u, v\right)\) 是必须边当且仅当 \(G_f\) 上存在路径 \(S \rightarrow u\) 和路径 \(v \rightarrow T\)。
可以发现因为 \(c_f(u, v) = 0\)，所以有 \(c_f(v, u) > 0\)，即边 \(\left(v, u\right) \in G_f\)，所以在 \(G_f\) 上存在路径 \(u \rightarrow v\) 等价于 \(u, v\) 在 \(G_f\) 上位于同一个强连通分量中。同理 \(G_f\) 上存在路径 \(S \rightarrow u\) 和路径 \(v \rightarrow T\) 等价于 \(u\) 和 \(S\) 在同一个强连通分量中且 \(v\) 和 \(T\) 在同一个强连通分量中。
Code
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<bool> bitset;
typedef std::tuple<valueType, valueType, valueType> ValueTuple;
typedef std::vector<ValueTuple> TupleVector;
class Dinic {
private:
struct Edge {
public:
typedef std::vector<Edge> container;
typedef container::iterator iterator;
valueType to;
valueType cap;
valueType flow;
iterator pair;
Edge() : to(-1), cap(-1), flow(-1), pair(){};
Edge(valueType to, valueType cap, iterator pair = iterator()) : to(to), cap(cap), flow(0), pair(pair){};
bool full() const {
return flow == cap;
}
};
typedef std::vector<ValueVector> Graph;
typedef std::vector<ValueVector::iterator> IterVector;
valueType N, M;
Edge::container edges;
Graph G;
ValueVector depth;
IterVector start;
ValueVector belong;
bitset inStack;
ValueVector dfn, low;
std::stack<valueType> stack;
bool Initialized;
public:
explicit Dinic(valueType N, valueType M) : N(N), M(M), edges((M << 1) + 10), G(N + 1), depth(N + 1, 0), start(N + 1), belong(N + 1, 0), inStack(N + 1, false), dfn(N + 1, 0), low(N + 1, 0), Initialized(false){};
void addEdge(valueType from, valueType to, valueType cap, valueType id) {
if (__builtin_expect(Initialized, false))
throw std::runtime_error("Dinic: addEdge after init");
edges[id << 1] = Edge(to, cap, std::next(edges.begin(), id << 1 | 1));
edges[id << 1 | 1] = Edge(from, 0, std::next(edges.begin(), id << 1));
G[from].emplace_back(id << 1);
G[to].emplace_back(id << 1 | 1);
}
void init() {
if (__builtin_expect(Initialized, false))
throw std::runtime_error("Dinic: init twice");
Initialized = true;
std::fill(depth.begin(), depth.end(), 0);
for (valueType i = 1; i <= N; ++i)
start[i] = G[i].begin();
}
void reset() {
if (__builtin_expect(!Initialized, false))
throw std::runtime_error("Dinic: reset before init");
for (valueType i = 1; i <= N; ++i)
for (auto &iter : G[i])
edges[iter].flow = 0;
std::fill(depth.begin(), depth.end(), 0);
Initialized = false;
}
valueType maxFlow(valueType S, valueType T) {
if (__builtin_expect(!Initialized, false))
throw std::runtime_error("Dinic: maxFlow before init");
valueType result = 0;
while (bfs(S, T)) {
IterVector begin = start;
result += dfs(S, T, std::numeric_limits<valueType>::max(), begin);
}
for (valueType i = 1; i <= N; ++i)
if (!dfn[i])
tarjan(i);
return result;
}
valueType scc(valueType n) const {
return belong[n];
}
bool full(valueType m) const {
return edges[m].full();
}
private:
bool bfs(valueType S, valueType T) {
std::fill(depth.begin(), depth.end(), 0);
std::queue<valueType> Q;
Q.push(S);
depth[S] = 1;
while (!Q.empty()) {
valueType const u = Q.front();
Q.pop();
for (auto const &iter : G[u]) {
auto const &e = edges[iter];
if ((e.cap > e.flow) && (!depth[e.to])) {
depth[e.to] = depth[u] + 1;
Q.push(e.to);
}
}
}
return depth[T] > 0;
}
valueType dfs(valueType u, valueType T, valueType flow, IterVector &Begin) {
if (u == T || flow == 0)
return flow;
valueType result = 0;
for (auto &iter = Begin[u]; iter != G[u].end(); ++iter) {
auto e = std::next(edges.begin(), *iter);
if (e->cap > e->flow && depth[e->to] == depth[u] + 1) {
valueType const f = dfs(e->to, T, std::min(flow - result, e->cap - e->flow), Begin);
e->flow += f;
e->pair->flow -= f;
result += f;
if (result == flow)
return flow;
}
}
return result;
}
void tarjan(valueType x) {
static valueType dfsCount = 0, sccCount = 0;
inStack[x] = true;
low[x] = dfn[x] = ++dfsCount;
stack.push(x);
for (auto const &iter : G[x]) {
auto e = std::next(edges.begin(), iter);
if (e->full())
continue;
if (!dfn[e->to]) {
tarjan(e->to);
low[x] = std::min(low[x], low[e->to]);
} else if (inStack[e->to]) {
low[x] = std::min(low[x], dfn[e->to]);
}
}
if (dfn[x] == low[x]) {
++sccCount;
valueType y;
do {
y = stack.top();
stack.pop();
inStack[y] = false;
belong[y] = sccCount;
} while (y != x);
}
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType N, M, S, T;
std::cin >> N >> M >> S >> T;
Dinic dinic(N, M);
TupleVector G;
G.reserve(M);
for (valueType i = 1; i <= M; ++i) {
valueType u, v, w;
std::cin >> u >> v >> w;
G.emplace_back(u, v, w);
dinic.addEdge(u, v, w, i);
}
dinic.init();
dinic.maxFlow(S, T);
for (valueType i = 0; i < M; ++i) {
valueType const id = i + 1;
auto const &[u, v, w] = G[i];
bool A = dinic.full(id << 1) && dinic.scc(u) != dinic.scc(v);
bool B = A && dinic.scc(S) == dinic.scc(u) && dinic.scc(T) == dinic.scc(v);
std::cout << A << ' ' << B << '\n';
}
std::cout << std::flush;
return 0;
}