โปรแกรมหาต้นทุนขั้นต่ำในการสร้างถนนเพื่อเดินทางจากเมืองแรกไปยังเมืองอื่นๆ ใน C++

สมมติว่าเรามีสองลิสต์ costs_from และ costs_to ที่มีขนาดเท่ากัน โดยดัชนี i แทนเมืองหนึ่ง การสร้างถนนทางเดียวจากเมือง i ไป j มีค่าใช้จ่ายเท่ากับ costs_from[i] + costs_to[j] นอกจากนี้ยังมีลิสต์ edges ที่แต่ละขอบมีรูปแบบ [x, y] แสดงว่ามีถนนทางเดียวจากเมือง x ไป y อยู่แล้ว หากเราต้องการเดินทางไปยังเมืองใดก็ได้จากเมือง 0 เราต้องหาต้นทุนขั้นต่ำในการสร้างถนนที่จำเป็น

ตัวอย่างเช่น หากอินพุตคือ costs_from = [6, 2, 2, 12], costs_to = [2, 2, 3, 2], edges = [[0, 3]] ผลลัพธ์จะเป็น 13 เนื่องจากเราสามารถเดินทางจาก 0 ไป 2 ด้วยต้นทุน 9 จากนั้นเดินทางจาก 2 ไป 1 ด้วยต้นทุน 4 และเรามีถนนจาก 0 ไป 3 อยู่แล้ว ดังนั้นรวมเป็น 9 + 4 = 13

ขั้นตอนการแก้ปัญหา

• n := ขนาดของ costs_from
• ret := 0
• กำหนดแมป edges และ redges สำหรับกราฟและกราฟย้อนกลับ
• สำหรับทุก it ใน g:
  • เพิ่ม it[1] เข้า edges[it[0]]
  • เพิ่ม it[0] เข้า redges[it[1]]
• from_cost := infinity
• กำหนดเซต visited และ reachable
• ฟังก์ชัน dfs(i):
  • ถ้า i ยังไม่ถูกเยี่ยมชมและไม่ถึงได้:
    • เพิ่ม i เข้า visited
    • สำหรับทุก j ใน edges[i] เรียก dfs(j)
    • เพิ่ม i เข้า po (post-order)
• ฟังก์ชัน dfs2(i):
  • ถ้า i อยู่ใน visited คืน true
  • ถ้า i อยู่ใน reachable คืน false
  • ทำเครื่องหมาย i ว่าเยี่ยมชมและถึงได้แล้ว
  • ret := true
  • สำหรับทุก j ใน redges[i] คำนวณ ret &= dfs2(j)
  • คืน ret
• คิว q เริ่มจากโหนด 0 เพื่อหาโหนดที่ถึงได้จากเมือง 0
• คำนวณ from_cost เป็นค่า costs_from ต่ำสุดของโหนดที่ถึงได้
• global_min := ค่า costs_from ต่ำสุดของทุกเมือง
• ret := ret + from_cost - global_min
• สร้างอาเรย์ po โดยเรียก dfs(i) สำหรับทุก i แล้วกลับลำดับ
• สำหรับแต่ละ i ใน po:
  • ถ้า i ถึงได้แล้ว ข้ามไป
  • เคลียร์ visited เรียก initial = dfs2(i)
  • ถ้า initial เป็นจริง:
    • หา best = ค่า costs_to ต่ำสุดใน visited
    • ret := ret + global_min + best
• คืนค่า ret

ตัวอย่างโค้ด C++

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

อินพุต

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

เอาต์พุต

13