Description
A,B 两个国家正在交战，其中A国的物资运输网中有 \(N\) 个中转站，\(M\) 条单向道路。设其中第 \(i\ (1\leq i\leq M)\) 条道路连接了 \(u_i,v_i\) 两个中转站，那么中转站 \(u_i\) 可以通过该道路到达 \(v_i\) 中转站，如果切断这条道路，需要代价 \(c_i\)。
现在B国想找出一个路径切断方案，使中转站 \(s\) 不能到达中转站 \(t\)，并且切断路径的代价之和最小。
小可可一眼就看出，这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题：
- 问题一：是否存在一个最小代价路径切断方案，其中该道路被切断？
- 问题二：是否对任何一个最小代价路径切断方案，都有该道路被切断？
现在请你回答这两个问题。
\(N\leq 4\times 10^3,M\times 6\times 10^4\)。
Solution
显然要先建图跑一遍最大流。
这时会发现残余网络上不是满流的边一定不为最小割上的边。因为让这条边的初始流量减去一个极小值后最大流结果不变，最小割也不变。但是如果这条边在任何一个最小割中就一定会让最小割减少，就矛盾了。所以结论是对的。
于是只有满流的边可能是最小割上的边，但是只有这个结论仍然无法判断一条边是否在最小割上。
注意到如果残余网络上存在一个环，那么把这个环上的初始流量均减 \(1\) 后最大流一定不变，所以这个环上的边也一定不为最小割边。
然后考虑缩点，只有缩点后 DAG 上的边可能为最小割边。
在这些边中只有直接连接 \(s\) 和 \(t\) 所在 scc 的边是必须边。
而对于 DAG 上其它边 \((u,v)\) 可以分别给出割和不割的构造：
- 割：让 \(s\to u\) 的路径为 \(A\) 集合，其余为 \(B\) 集合。
- 不割：如果 \(u\) 为 \(s\)，则 \(v\) 一定不为 \(t\)，让 \(s\to u\to v\) 的路径为 \(A\) 集合，其余为 \(B\) 集合。否则让 \(u\to v\to t\) 为 \(A\) 集合，其余为 \(B\) 集合。
所以 DAG 上的所有边均为可行边，连接 \(s\) 和 \(t\) 所在 scc 的边为必须边。
时间复杂度：\(O(N^2M)\)。
Code
#include <bits/stdc++.h>
// #define int int64_t
const int kMaxN = 4e3 + 5, kMaxM = 2e5 + 5, kInf = 1e9;
int n, m, s, t, tot;
int u[kMaxM], v[kMaxM], w[kMaxM];
int dfn[kMaxN], low[kMaxN], bel[kMaxN];
bool ins[kMaxN], res[kMaxM][2];
std::vector<std::pair<int, int>> G[kMaxN];
namespace Dinic {
struct Edge {
int v, w, pre;
} e[kMaxM * 2];
int tot = 1, flow, n, s, t;
int tail[kMaxN], cur[kMaxN], dep[kMaxN];
void adde(int u, int v, int w) { e[++tot] = {v, w, tail[u]}, tail[u] = tot; }
void add(int u, int v, int w) { adde(u, v, w), adde(v, u, 0); }
void clear() {
for (int i = 0; i <= n; ++i) tail[i] = 0;
for (int i = 0; i <= tot; ++i) e[i] = {0, 0, 0};
flow = 0, tot = 1;
}
void init(int _n, int _s, int _t) { clear(); n = _n, s = _s, t = _t; }
bool bfs() {
static bool vis[kMaxN] = {0};
std::queue<int> q;
for (int i = 1; i <= n; ++i)
cur[i] = tail[i], dep[i] = 1e9, vis[i] = 0;
q.emplace(s), dep[s] = 0, vis[s] = 1;
for (; !q.empty();) {
int u = q.front(); q.pop();
if (u == t) return 1;
for (int i = tail[u]; i; i = e[i].pre) {
int v = e[i].v, w = e[i].w;
if (w && !vis[v]) {
dep[v] = dep[u] + 1, vis[v] = 1, q.emplace(v);
}
}
}
return 0;
}
int dfs(int u, int lim) {
if (u == t || !lim) return lim;
int flow = 0;
for (int &i = cur[u]; i; i = e[i].pre) {
int v = e[i].v, w = e[i].w;
if (w && dep[v] == dep[u] + 1) {
int fl = dfs(v, std::min(lim, w));
if (!fl) dep[v] = 1e9;
lim -= fl, flow += fl;
e[i].w -= fl, e[i ^ 1].w += fl;
if (!lim) break;
}
}
return flow;
}
int maxflow() {
int flow = 0;
for (; bfs(); flow += dfs(s, kInf)) {}
return flow;
}
} // namespace Dinic
void dfs(int u) {
static int cnt = 0;
static std::stack<int> stk;
dfn[u] = low[u] = ++cnt, stk.emplace(u), ins[u] = 1;
for (auto [v, id] : G[u]) {
if (!dfn[v]) {
dfs(v), low[u] = std::min(low[u], low[v]);
} else if (ins[v]) {
low[u] = std::min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
++tot;
for (; !stk.empty();) {
int t = stk.top(); stk.pop();
bel[t] = tot, ins[t] = 0;
if (t == u) break;
}
}
}
void dickdreamer() {
std::cin >> n >> m >> s >> t;
Dinic::init(n, s, t);
for (int i = 1; i <= m; ++i) {
std::cin >> u[i] >> v[i] >> w[i];
Dinic::add(u[i], v[i], w[i]);
}
Dinic::maxflow();
for (int i = 2; i <= Dinic::tot; ++i) {
if (Dinic::e[i].w) {
G[Dinic::e[i ^ 1].v].emplace_back(Dinic::e[i].v, i / 2);
}
}
for (int i = 1; i <= n; ++i)
if (!dfn[i])
dfs(i);
for (int i = 1; i <= m; ++i) {
if (!Dinic::e[2 * i].w) {
res[i][0] = (bel[u[i]] != bel[v[i]]);
res[i][1] = (bel[u[i]] == bel[s] && bel[v[i]] == bel[t]);
std::cout << res[i][0] << ' ' << res[i][1] << '\n';
} else {
std::cout << "0 0\n";
}
}
}
int32_t main() {
#ifdef ORZXKR
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
int T = 1;
// std::cin >> T;
while (T--) dickdreamer();
// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
return 0;
}