Hướng dẫn giải của Cycle Free Flow


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: Mike4235

Lời giải

Để hiểu cách giải bài này, bạn phải hiểu cách giải bài Sloth Naptime.

Ta thấy rằng đồ thị liên thông và không có chu trình, khuyên hay cạnh trùng nên đồ thị được cho là một cây. Qua đó dễ dàng nhận thấy rằng luồng cực đại giữa hai đỉnh chính là giá trị của cạnh có trọng số thấp nhất trong đường đi ngắn nhất giữa hai đỉnh.

Tương tự bài Sloth Naptime, ta sẽ dựng mảng ~up~ để tìm ~lca~ của hai đỉnh, sau đó ta dựng thêm một mảng ~flow~ với ~flow[i][j]~ là giá trị của cạnh bé nhất trong đường đi từ đỉnh ~i~ đến tổ tiên thứ ~2^j~ của đỉnh ~i~. Gần như tương tự mảng ~up~, ta có công thức ~flow[i][j] = min(flow[i][j - 1], flow[up[i][j - 1]][j - 1])~.

Vậy để trả lời mỗi truy vấn hai đỉnh ~a~ và ~b~, ta sẽ tìm giá trị của cạnh bé nhất từ ~a~ đến ~lca(a, b)~ và của cạnh bé nhất từ ~b~ đến ~lca(a, b)~ tương tự cách tìm tổ tiên thứ ~k~ của một đỉnh. Đáp án của truy vấn sẽ là là giá trị bé hơn.

Tổng độ phức tạp: ~\mathcal{O}(n\log{n} + q\log{n})~.

Code mẫu

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 5;
const int INF = 2e9;

int n, m, q, d[N], up[N][19], flow[N][19];
vector<pair<int, int>> adj[N];

void pre_dfs(int u, int p, int w) {
    up[u][0] = p;
    flow[u][0] = w;
    for (int i = 1; i <= 18; i++) {
        up[u][i] = up[up[u][i - 1]][i - 1];
        flow[u][i] = min(flow[u][i - 1], flow[up[u][i - 1]][i - 1]);
    }

    for (auto e : adj[u]) {
        int v = e.first, w = e.second;
        if (v == p) continue;
        d[v] = d[u] + 1;
        pre_dfs(v, u, w);
    }
}

int query(int u, int v) {
    if (d[u] > d[v]) swap(u, v);

    int res = INF;
    for (int i = 18; i >= 0; i--)
        if ((d[v] - d[u]) >> i & 1) {
            res = min(res, flow[v][i]);
            v = up[v][i];
        }

    if (u == v) return res;

    for (int i = 18; i >= 0; i--)
        if (up[u][i] != up[v][i]) {
            res = min(res, flow[u][i]);
            res = min(res, flow[v][i]);
            u = up[u][i];
            v = up[v][i];
        }

    res = min(res, flow[u][0]);
    res = min(res, flow[v][0]);

    return res;
}

signed main() {
    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 1, a, b, w; i <= m; i++) {
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }

    pre_dfs(1, 0, 0);

    cin >> q;
    for (int a, b; q--; ) {
        cin >> a >> b;     
        cout << query(a, b) << '\n';
    }
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.