Hướng giải của Mạng lưới dày đặc

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Thuật toán Floyd-Warshall động thêm đỉnh ngược thời gian. Việc xóa đỉnh khỏi đồ thị và tính lại tổng khoảng cách ngắn nhất rất khó làm trực tiếp trong thời gian tối ưu. Tuy nhiên, ta có thể đảo ngược toàn bộ quy trình: bắt đầu với đồ thị trống và thêm lần lượt các đỉnh theo thứ tự ngược lại (từ đỉnh bị xóa cuối cùng trở về đỉnh bị xóa đầu tiên). Khi thêm một đỉnh \(k\) vào tập đỉnh hoạt động:

  1. Cập nhật khoảng cách từ các đỉnh hoạt động khác tới \(k\) và ngược lại.
  2. Thư giãn mọi cặp đỉnh hoạt động \(i, j\) thông qua đỉnh \(k\). Sau mỗi lần thêm đỉnh, ta tính tổng khoảng cách ngắn nhất giữa các cặp đỉnh hoạt động và lưu lại kết quả để in ra theo thứ tự ban đầu.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<vector<long long>> adj(n + 1, vector<long long>(n + 1, INF));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            long long val;
            cin >> val;
            if (i == j) adj[i][j] = 0;
            else if (val != -1) adj[i][j] = val;
        }
    }

    int q;
    if (!(cin >> q)) return 0;

    vector<int> removed(q);
    vector<bool> is_removed(n + 1, false);
    for (int i = 0; i < q; i++) {
        cin >> removed[i];
        is_removed[removed[i]] = true;
    }

    vector<int> active;
    vector<bool> is_active(n + 1, false);
    for (int i = 1; i <= n; i++) {
        if (!is_removed[i]) {
            active.push_back(i);
            is_active[i] = true;
        }
    }

    vector<vector<long long>> dist(n + 1, vector<long long>(n + 1, INF));
    for (int i = 1; i <= n; i++) dist[i][i] = 0;
    for (int i : active) {
        for (int j : active) {
            dist[i][j] = adj[i][j];
        }
    }

    for (int k : active) {
        for (int i : active) {
            for (int j : active) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    vector<long long> results(q);
    for (int idx = q - 1; idx >= 0; idx--) {
        int k = removed[idx];

        long long current_sum = 0;
        for (int i : active) {
            for (int j : active) {
                if (i != j && dist[i][j] != INF) {
                    current_sum += dist[i][j];
                }
            }
        }
        results[idx] = current_sum;

        active.push_back(k);
        is_active[k] = true;

        for (int i : active) {
            dist[i][k] = adj[i][k];
            dist[k][i] = adj[k][i];
        }
        dist[k][k] = 0;

        for (int i : active) {
            for (int j : active) {
                if (dist[i][j] != INF && adj[j][k] != INF) {
                    dist[i][k] = min(dist[i][k], dist[i][j] + adj[j][k]);
                }
                if (adj[k][j] != INF && dist[j][i] != INF) {
                    dist[k][i] = min(dist[k][i], adj[k][j] + dist[j][i]);
                }
            }
        }

        for (int i : active) {
            for (int j : active) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    for (int i = 0; i < q; i++) {
        cout << results[i] << "\n";
    }

    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.