Chương trình tìm số lượng đường đi tối thiểu cần xây dựng để đến được mọi thành phố từ thành phố đầu tiên trong C++

Giả sử chúng ta có hai danh sách costs_from và costs_to cùng kích thước, trong đó mỗi chỉ số i đại diện cho một thành phố. Việc xây dựng một đường đi một chiều từ thành phố i đến j có chi phí là costs_from[i] + costs_to[j]. Chúng ta cũng có một danh sách các cạnh edges trong đó mỗi cạnh [x, y] cho biết đã có sẵn một đường đi một chiều từ thành phố x đến y. Nếu muốn đi đến bất kỳ thành phố nào từ thành phố 0, ta cần tìm chi phí tối thiểu để xây dựng các đường đi cần thiết.

Ví dụ, với đầu vào costs_from = [6, 2, 2, 12], costs_to = [2, 2, 3, 2], edges = [[0, 3]], kết quả sẽ là 13. Ta có thể đi từ 0 đến 2 với chi phí 9 (6+3), sau đó từ 2 đến 1 với chi phí 4 (2+2). Đường đi đến 3 từ 0 đã có sẵn. Tổng chi phí: 9 + 4 = 13.

Giải thuật

Các bước thực hiện như sau:

• n := kích thước của costs_from
• ret := 0
• Định nghĩa hai map edges và redges (cạnh ngược)
• Duyệt qua tất cả các phần tử it trong g:
  • Thêm it[1] vào edges[it[0]]
  • Thêm it[0] vào redges[it[1]]
• from_cost := vô cực
• Định nghĩa tập hợp visited và reachable
• Định nghĩa hàm dfs(i):
  • Nếu i chưa được thăm và chưa thể đến được:
    • Đánh dấu i đã thăm
    • Đệ quy dfs(j) cho mọi j trong edges[i]
    • Thêm i vào mảng po (thứ tự hậu tố)
• Định nghĩa hàm dfs2(i):
  • Nếu i đã thăm → trả về true
  • Nếu i đã có thể đến được → trả về false
  • Đánh dấu i đã thăm và có thể đến được
  • ret := true
  • Với mọi j trong redges[i]: ret &= dfs2(j)
  • Trả về ret
• Khởi tạo hàng đợi q, thêm 0 vào reachable và q
• Khi q không rỗng:
  • Lấy phần tử đầu node và loại bỏ khỏi q
  • Với mọi i trong edges[node]:
    • Nếu i chưa trong reachable: thêm vào reachable và q
  • Cập nhật from_cost = min(from_cost, costs_from[node])
• global_min := phần tử nhỏ nhất của costs_from
• ret := ret + from_cost - global_min
• Định nghĩa mảng po
• Với i từ 0 đến n-1: gọi dfs(i)
• Đảo ngược mảng po
• Với mỗi i trong po:
  • Nếu i đã trong reachable: bỏ qua
  • Xóa visited
  • initial := dfs2(i)
  • Nếu initial là true:
    • best := inf
    • Với mọi j trong visited: best = min(best, costs_to[j])
    • ret := ret + global_min + best
• Trả về ret

Ví dụ minh họa

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

class Solution {
public:
    int solve(vector<int>& costs_from, vector<int>& costs_to, vector<vector<int>>& g) {
        int n = costs_from.size();
        int ret = 0;
        map<int, vector<int>> edges;
        map<int, vector<int>> redges;
        for (auto& it : g) {
            edges[it[0]].push_back(it[1]);
            redges[it[1]].push_back(it[0]);
        }
        int from_cost = INT_MAX;
        set<int> visited;
        set<int> reachable;
        queue<int> q;
        reachable.insert(0);
        q.push(0);
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            for (int i : edges[node]) {
                if (!reachable.count(i)) {
                    reachable.insert(i);
                    q.push(i);
                }
            }
            from_cost = min(from_cost, costs_from[node]);
        }
        int global_min = *min_element(costs_from.begin(), costs_from.end());
        ret += from_cost - global_min;
        vector<int> po;
        function<void(int)> dfs = [&](int i) {
            if (!visited.count(i) && !reachable.count(i)) {
                visited.insert(i);
                for (int j : edges[i]) {
                    dfs(j);
                }
                po.push_back(i);
            }
        };
        for (int i = 0; i < n; i++) dfs(i);
        reverse(po.begin(), po.end());
        function<bool(int)> dfs2 = [&](int i) {
            if (visited.count(i)) return true;
            if (reachable.count(i)) return false;
            visited.insert(i);
            reachable.insert(i);
            bool ret = true;
            for (int j : redges[i]) {
                ret &= dfs2(j);
            }
            return ret;
        };
        for (int i : po) {
            if (reachable.count(i)) continue;
            visited.clear();
            bool initial = dfs2(i);
            if (initial) {
                int best = INT_MAX;
                for (int j : visited) {
                    best = min(best, costs_to[j]);
                }
                ret += global_min + best;
            }
        }
        return ret;
    }
};

int solve(vector<int>& costs_from, vector<int>& costs_to, vector<vector<int>>& edges) {
    return (new Solution())->solve(costs_from, costs_to, edges);
}

int main() {
    vector<int> costs_from = {6, 2, 2, 12};
    vector<int> costs_to = {2, 2, 3, 2};
    vector<vector<int>> edges = {{0, 3}};
    cout << solve(costs_from, costs_to, edges);
}

Đầu vào

{6, 2, 2, 12}, {2, 2, 3, 2}, {{0, 3}}

Đầu ra

13