Giả sử chúng ta có hai danh sách Cost_from và Cost_to có cùng kích thước, trong đó mỗi chỉ mục tôi đại diện cho một thành phố. Nó đang làm đường một chiều từ thành phố i đến j và chi phí của chúng là Cost_from [i] + Cost_to [j]. Chúng tôi cũng có danh sách các cạnh mà mỗi cạnh chứa [x, y] cho biết đã có đường một chiều từ thành phố x đến y. Nếu chúng ta muốn đi đến bất kỳ thành phố nào từ thành phố 0, chúng ta phải tìm chi phí tối thiểu để xây dựng những con đường cần thiết.
Vì vậy, nếu đầu vào giống như Cost_from =[6, 2, 2, 12] Cost_to =[2, 2, 3, 2] edge =[[0, 3]], thì đầu ra sẽ là 13, như chúng ta có thể từ 0 đến 2 với chi phí là 9. Sau đó, chúng ta có thể đi từ 2 đến 1 với chi phí là 4. Và chúng ta đã có đường để đi đến 3 từ 0. Vậy tổng là 9 + 4 =13.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- n:=kích thước của chi phí_từ chỗ
- ret:=0
- Xác định hai cạnh bản đồ và dấu gạch đỏ
- cho tất cả các mục trong g:
- chèn nó [1] vào cuối các cạnh [nó [0]]
- chèn nó [0] vào cuối các dấu đỏ [nó [1]]
- from_cost:=inf
- Xác định một nhóm đã truy cập và một nhóm khác có thể truy cập được
- xác định một hàm dfs, điều này sẽ nhận một số i
- nếu tôi không được truy cập và tôi không thể liên lạc được, thì:
- chèn tôi vào đã thăm
- đối với tất cả j trong các cạnh [i], thực hiện
- dfs (j)
- chèn tôi vào cuối trang
- nếu tôi không được truy cập và tôi không thể liên lạc được, thì:
- xác định một hàm dfs2, hàm này sẽ nhận một số i
- nếu tôi được truy cập, thì
- trả về true
- nếu tôi có thể truy cập được
- trả về false
- đánh dấu tôi là đã ghé thăm và đánh dấu tôi là có thể liên hệ được
- ret:=true
- đối với tất cả j trong dấu đỏ [i], thực hiện
- ret:+ ret VÀ dfs2 (j)
- trả lời lại
- Xác định một hàng đợi q
- chèn 0 vào có thể truy cập và chèn 0 vào q
- while (q không trống), thực hiện:
- node:=phần tử đầu tiên của q
- xóa phần tử khỏi q
- cho mỗi i trong các cạnh [nút]
- nếu tôi không thể truy cập được, thì:
- chèn i vào có thể truy cập, chèn i vào q
- from_cost:=tối thiểu from_cost và Cost_from [node]
- nếu tôi không thể truy cập được, thì:
- global_min:=phần tử tối thiểu của Cost_from
- ret:=ret + from_cost - global_min
- Xác định po mảng
- đối với tôi trong phạm vi từ 0 đến n, thực hiện
- dfs (i)
- đảo ngược po mảng
- đối với mỗi tôi trong po, thực hiện
- nếu tôi có thể truy cập được, thì:
- chuyển sang lần lặp tiếp theo
- xóa mảng đã truy cập
- ban đầu:=dfs2 (i)
- nếu ban đầu là true, thì:
- tốt nhất:=inf
- cho mỗi j trong đã truy cập:
- tốt nhất:=tối thiểu trong số tốt nhất và giá_đến [j]
- ret:=ret + global_min + best
- nếu tôi có thể truy cập được, thì:
- trả lời lại
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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);
} Đầu vào
{6, 2, 2, 12}, {2, 2, 3, 2}, {{0, 3}} Đầu ra
13