700C

WIDA · 2023-09-28 21:31:39 · 题解

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 或更高版本的编译器~

暴力枚举

#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;
}();

网络流

#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;
}();