700C

## 700C（$\tt *2600$；图论-缩点、网络流-最小割） > 一些废话：讲道理我本不该写这篇题解，但是看了一眼这道题的题解区感觉大家讲的都比较杂，百度了一下发现也是如此 ~~可能佬们都觉得这题太基础了所以不愿意多讲~~ 所以我作为一只菜鸟，来综合整理一下。  需要分类讨论： - 不需要删边的情况可以很简单的维护搞定（即为判断 $s$ 和 $t$ 是否位于同一个连通块，方法很多，略）； - 删去一条边的情况即为删去“有效”割边，这里的“有效”指的是位于 $s$ 到 $t$ 的路径上的割边（例如样例一中 $4-5$ 这一条边就不是“有效”的）；我们可以使用 Tarjan 找出全部割边，再使用 dfs 维护有效路径，综合两者即可搞定这一情况； - 删去两条边的情况有两种做法，其一是暴力枚举，其二是使用网络流求解最小割，随后在残余网络寻找答案，需要较高技巧。下方我将分别讲解。 ### 暴力枚举 容易发现最短路径不经过超过 $N$ 个点，所以我们依次枚举 $s$ 到 $t$ 最短路径上的每一条边，然后建立一张不包含这一条边的图，重复上述“删去一条边”的操作。 分析复杂度，我们至多将建立 $N$ 张不同的图，单次查找割边的复杂度为 $\mathcal O(N+M)$ ，所以可以在 $\mathcal O(NM)$ 级别的复杂度内完成。 需要注意的是，非最短路径理论上也可做，但是我的写法超时了，所以改成了最短路径。这一做法细节较多，需要谨慎书写。 ### 优雅网络流 ~~如果你没有学习过网络流，那么可以无视这一做法。~~ 考虑最小割模型。 首先，对于此前求解出的全部割边，我们显然不能将它们割掉，所以它们的边权置为 $\infty$；对于其他边，由于需要解决“删去**两条边**”最小割，所以我们将全部边的边权加上一个不小于总边权之和的基数 $B$，如此一来，求出的答案在 $[2B,3B)$ 这一范围内时即等价于“删去两条边”的最小割（这一步很巧妙）。 随后我们遍历残留网络获取答案。根据最大流的原理，如果某条边是合法的答案，那么这条边之前的残余流量一定非零，这条边和这条边之后的残余流量一定为零，所以我们只需要使用 dfs 沿着有残余流量的边一路搜索，很容易即可找到目标边。 ### 代码环节 首先声明，我并不是 OI 出身，所以码风和正常 OI 不太一样，如果你熟悉 CodeForces 风格那会比较适应；同时我还是个封装怪和 STL 喜爱者，本题中 Tarjan 和网络流的算法细节都依赖于结构体封装实现，数据结构都依赖于 STL，请各位大佬谨慎参考！ 对了，如果要在本地进行测试，您可能需要使用 C++17 或更高版本的编译器~ 暴力枚举 ```cpp #include <bits/stdc++.h> using namespace std; struct E_DCC { int n; vector<int> h, ver, ne; vector<int> dfn, low, col, S; int now, cnt, tot; vector<bool> bridge; // 记录是否是割边 E_DCC(int n, int m) : n(n) { m *= 2; // 注意链式前向星边的数量翻倍 ver.resize(m + 1); ne.resize(m + 1); bridge.resize(m + 1); h.resize(n + 1, -1); dfn.resize(n + 1); low.resize(n + 1); col.resize(n + 1); S.clear(); tot = cnt = now = 0; } void add(int x, int y) { // 注意，这里的编号从 0 开始 ver[tot] = y, ne[tot] = h[x], h[x] = tot++; ver[tot] = x, ne[tot] = h[y], h[y] = tot++; } void tarjan(int x, int fa) { // 这里是缩边双，不是缩点，不相同 dfn[x] = low[x] = ++now; S.push_back(x); for (int i = h[x]; ~i; i = ne[i]) { int y = ver[i]; if (!dfn[y]) { tarjan(y, i); // 这里储存的是父亲边的编号 low[x] = min(low[x], low[y]); // y 不能到达 x 的任何一个祖先节点，(x - y) 即为一条割边 // 但是在这里，我们不直接储存 (x - y) 这条边，而是储存边的编号 // 这样做是为了处理重边的情况（点可能相同，但是边的编号绝对不相同） if (dfn[x] < low[y]) { bridge[i] = bridge[i ^ 1] = true; } } else if (i != (fa ^ 1)) { // 这里同样的，使用边的编号来处理重边情况 low[x] = min(low[x], dfn[y]); } } if (dfn[x] == low[x]) { int pre = 0; cnt++; do { pre = S.back(); S.pop_back(); col[pre] = cnt; } while (pre != x); } } set<array<int, 2>> work() { // [新图的顶点数量, 新图] for (int i = 1; i <= n; i++) { // 避免图不连通 if (dfn[i] == 0) { tarjan(i, -1); } } set<array<int, 2>> ans; for (int i = 0; i < tot; ++i) { if (bridge[i]) { // 如果 (i, i ^ 1) 是割边 ans.insert({ver[i], ver[i ^ 1]}); } } return ans; } }; signed main() { int n, m, s, t; cin >> n >> m >> s >> t; E_DCC scc(n, m); vector<vector<array<int, 3>>> ver(n + 1); vector<array<int, 4>> edge; for (int i = 1; i <= m; i++) { int x, y, w; cin >> x >> y >> w; scc.add(x, y); ver[x].push_back({y, w, i}); ver[y].push_back({x, w, i}); edge.push_back({x, y, w, i}); } vector<int> vis(n + 1), type(n + 1); type[t] = 1; auto zero = [&](auto self, int x, int fa) -> void { vis[x] = 1; for (auto [y, w, id] : ver[x]) { if (y == fa) continue; type[x] |= type[y]; if (vis[y]) continue; self(self, y, x); type[x] |= type[y]; } }; zero(zero, s, 0); if (!vis[t]) { // 特判不连通 cout << 0 << '\n'; cout << 0 << '\n'; return 0; } int ans = 2E9 + 7; vector<int> Id; auto chk = scc.work(); for (auto [x, y, w, id] : edge) { if (chk.count({x, y}) && w < ans && type[x] && type[y]) { ans = w; Id = {id}; } } queue<int> q; q.push(s); vector<int> fa(n + 1); map<array<int, 2>, array<int, 2>> dic; fa[s] = -1; while (q.size()) { int x = q.front(); q.pop(); for (auto [y, w, id] : ver[x]) { if (fa[y]) continue; fa[y] = x; dic[{x, y}] = {id, w}; q.push(y); } } vector<array<int, 2>> path; int now = t; while (true) { path.push_back(dic[{fa[now], now}]); now = fa[now]; if (now == s) break; } for (auto [id_, w_] : path) { E_DCC graph(n, m); for (auto [x, y, w, id] : edge) { if (id == id_) continue; graph.add(x, y); } vis.assign(n + 1, 0); type.assign(n + 1, 0); type[t] = 1; auto dfs = [&](auto self, int x, int fa) -> void { vis[x] = 1; for (auto [y, w, id] : ver[x]) { if (y == fa || id == id_) continue; type[x] |= type[y]; if (vis[y]) continue; self(self, y, x); type[x] |= type[y]; } }; dfs(dfs, s, 0); auto chk = graph.work(); for (auto [x, y, w, id] : edge) { if (id != id_ && chk.count({x, y}) && w + w_ < ans && type[x] && type[y]) { ans = w + w_; Id = {id, id_}; } } } if (ans == 2E9 + 7) { cout << -1 << '\n'; } else { cout << ans << '\n'; cout << Id.size() << '\n'; for (auto it : Id) { cout << it << ' '; } } } int __OI_INIT__ = []() { ios::sync_with_stdio(0), cin.tie(0); cout.tie(0); cout << fixed << setprecision(12); return 0; }(); ``` 网络流 ```cpp #define int long long template <typename T> struct Flow_ { const int n; const T inf = numeric_limits<T>::max(); struct Edge { int to; T w; Edge(int to, T w) : to(to), w(w) {} }; vector<Edge> ver; vector<vector<int>> h; vector<int> cur, d; Flow_(int n) : n(n + 1), h(n + 1) {} void add(int u, int v, T c) { h[u].push_back(ver.size()); ver.emplace_back(v, c); h[v].push_back(ver.size()); ver.emplace_back(u, 0); } bool bfs(int s, int t) { d.assign(n, -1); d[s] = 0; queue<int> q; q.push(s); while (!q.empty()) { auto x = q.front(); q.pop(); for (auto it : h[x]) { auto [y, w] = ver[it]; if (w && d[y] == -1) { d[y] = d[x] + 1; if (y == t) return true; q.push(y); } } } return false; } T dfs(int u, int t, T f) { if (u == t) return f; auto r = f; for (int &i = cur[u]; i < h[u].size(); i++) { auto j = h[u][i]; auto &[v, c] = ver[j]; auto &[u, rc] = ver[j ^ 1]; if (c && d[v] == d[u] + 1) { auto a = dfs(v, t, std::min(r, c)); c -= a; rc += a; r -= a; if (!r) return f; } } return f - r; } T work(int s, int t) { T ans = 0; while (bfs(s, t)) { cur.assign(n, 0); ans += dfs(s, t, inf); } return ans; } vector<int> get(int s) { vector<int> vis(n + 1); auto dfs = [&](auto self, int x) -> void { vis[x] = 1; for (auto it : h[x]) { auto [y, w] = ver[it]; if (!vis[y] && w) { self(self, y); } } }; dfs(dfs, s); return vis; } }; using Flow = Flow_<int>; signed main() { int n, m, s, t; cin >> n >> m >> s >> t; E_DCC scc(n, m); vector<vector<array<int, 3>>> ver(n + 1); vector<array<int, 4>> edge; for (int i = 1; i <= m; i++) { int x, y, w; cin >> x >> y >> w; scc.add(x, y); ver[x].push_back({y, w, i}); ver[y].push_back({x, w, i}); edge.push_back({x, y, w, i}); } vector<int> vis(n + 1), type(n + 1); type[t] = 1; auto zero = [&](auto self, int x, int fa) -> void { vis[x] = 1; for (auto [y, w, id] : ver[x]) { if (y == fa) continue; type[x] |= type[y]; if (vis[y]) continue; self(self, y, x); type[x] |= type[y]; } }; zero(zero, s, 0); if (!vis[t]) { // 特判不连通 cout << 0 << '\n'; cout << 0 << '\n'; return 0; } Flow flow(n); int ans = 1E18; vector<int> Id; auto chk = scc.work(); for (auto [x, y, w, id] : edge) { if (chk.count({x, y}) && w < ans && type[x] && type[y]) { ans = w; Id = {id}; } if (chk.count({x, y})) { flow.add(x, y, 1E18); flow.add(y, x, 1E18); } else { flow.add(x, y, w + 1E14); flow.add(y, x, w + 1E14); } } int f = flow.work(s, t) - 2E14; if (0 <= f && f < 1E14 && ans > f) { ans = f; Id.clear(); auto flag = flow.get(s); for (auto [x, y, w, id] : edge) { if (flag[x] ^ flag[y]) { Id.push_back(id); } } } if (ans == 1E18) { cout << -1 << '\n'; } else { cout << ans << '\n'; cout << Id.size() << '\n'; for (auto it : Id) { cout << it << ' '; } } } int __OI_INIT__ = []() { ios::sync_with_stdio(0), cin.tie(0); cout.tie(0); cout << fixed << setprecision(12); return 0; }(); ```