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

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

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

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ cost_from
• ret :=0
• กำหนดสองขอบและขอบของแผนที่
• สำหรับรายการทั้งหมดใน g:
  • ใส่มัน[1] ที่ส่วนท้ายของขอบ[it[0]]
  • แทรก it[0] ที่ส่วนท้ายของสีแดง[it[1]]
• from_cost :=inf
• กำหนดหนึ่งชุดที่เข้าชมและอีกชุดที่เข้าถึงได้
• กำหนดฟังก์ชัน dfs ซึ่งจะใช้ตัวเลข i
  • ถ้าฉันไม่ได้มาเยี่ยมและไม่สามารถเข้าถึงได้ ดังนั้น:
    • แทรกฉันเข้าไปในการเยี่ยมชม
    • สำหรับ j in edge[i] ทั้งหมด ให้ทำ
      • dfs(j)
    • ใส่ i ต่อท้าย po
• กำหนดฟังก์ชัน dfs2 ซึ่งจะใช้ตัวเลข i
• ถ้าฉันมาเยี่ยมแล้ว
  • คืนค่าจริง
• ถ้าฉันสามารถเข้าถึงได้
  • คืนค่าเท็จ
• ทำเครื่องหมายว่าเยี่ยมชมแล้วและทำเครื่องหมายว่าเข้าถึงได้
• ret :=true
• สำหรับ j ใน redges[i], do
  • ret :+ ret และ dfs2(j)
• คืนสินค้า
• กำหนดหนึ่งคิว q
• แทรก 0 เข้าไปที่เข้าถึงได้ และแทรก 0 ลงใน q
• ในขณะที่ (q ไม่ว่าง) ให้ทำ:
  • โหนด :=องค์ประกอบแรกของ q
  • ลบองค์ประกอบออกจาก q
  • สำหรับแต่ละ i ใน edge[node]
    • หากฉันไม่สามารถเข้าถึงได้แล้ว:
      • แทรก i เข้าไป แทรก i เข้าไปใน q
    • from_cost :=ขั้นต่ำของ from_cost และ cost_from[node]
• global_min :=องค์ประกอบขั้นต่ำของ cost_from
• ret :=ret + from_cost - global_min
• กำหนดอาร์เรย์ po
• สำหรับ i ในช่วง 0 ถึง n ให้ทำ
  • dfs(i)
• ย้อนกลับอาร์เรย์ po
• สำหรับแต่ละ i ใน po ทำ
  • ถ้าฉันสามารถเข้าถึงได้แล้ว:
    • ติดตามตอนต่อไป
  • ล้างอาร์เรย์ที่เข้าชม
  • ค่าเริ่มต้น :=dfs2(i)
  • ถ้าเริ่มต้นเป็นจริง ดังนั้น:
    • ดีที่สุด :=inf
    • สำหรับแต่ละ j ในการเยี่ยมชม:
      • ดีที่สุด :=ขั้นต่ำสุดและ cost_to[j]
    • ret :=ret + global_min + ดีที่สุด
• คืนสินค้า

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include
using namespace std;
class Solution {
   public:
   int solve(vector& costs_from, vector& costs_to, vector>& g) {
      int n = costs_from.size();
      int ret = 0;
      map> edges;
      map> 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 visited;
      set reachable;
      queue 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 po;
      function dfs;
      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 dfs2;
      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& costs_from, vector& costs_to, vector>& edges) {
   return (new Solution())->solve(costs_from, costs_to, edges);
}
int main(){
   vector costs_from = {6, 2, 2, 12};
   vector costs_to = {2, 2, 3, 2};
   vector> edges = {{0, 3}};
   cout << solve(costs_from, costs_to, edges);
}

อินพุต

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

ผลลัพธ์

13