P4126 [AHOI2009] 最小割 题解

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)$ 可以分别给出割和不割的构造：

1. 割：让 $s\to u$ 的路径为 $A$ 集合，其余为 $B$ 集合。
2. 不割：如果 $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;
}