각 인덱스 i가 도시를 나타내는 동일한 크기의 두 목록 cost_from 및 cost_to가 있다고 가정합니다. 그것은 도시 i에서 j까지 일방통행 도로를 만들고 있으며 비용은 비용_from[i] + 비용_to[j]입니다. 또한 각 모서리에 [x, y]가 포함된 모서리 목록이 있으며 이는 x에서 y로 가는 일방통행 도로가 이미 있음을 나타냅니다. 0번 도시에서 아무 도시로 가려면 필요한 도로를 건설하는 데 필요한 최소 비용을 찾아야 합니다.
따라서 입력이 cost_from =[6, 2, 2, 12] cost_to =[2, 2, 3, 2] edge =[[0, 3]]인 경우 출력은 13이 됩니다. 비용 9로 0에서 2로. 그 후 비용 4로 2에서 1로 갈 수 있습니다. 그리고 이미 0에서 3으로 가는 길이 있습니다. 따라서 합계는 9 + 4 =13입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n :=cost_from 의 크기
- ret :=0
- 두 개의 지도 가장자리 및 가장자리 정의
- 모든 항목에 대해 g:
- 가장자리의 끝에 삽입[1][it[0]]
- 가장자리[it[1]] 끝에 삽입[0]
- from_cost :=정보
- 방문한 세트와 도달 가능한 다른 세트 정의
- 함수 dfs를 정의하면 숫자 i
- 가 필요합니다.
- 방문하지 않고 연결할 수 없는 경우:
- 방문한 항목에 i 삽입
- 가장자리[i]의 모든 j에 대해 다음을 수행합니다.
- dfs(j)
- po 끝에 i 삽입
- 방문하지 않고 연결할 수 없는 경우:
- 함수 dfs2를 정의합니다. 여기에는 숫자 i가 필요합니다.
- 내가 방문하면
- 참을 반환
- 연결 가능한 경우
- 거짓 반환
- 방문한 것으로 표시하고 연결 가능한 것으로 표시
- ret :=사실
- redges[i]의 모든 j에 대해 수행
- ret :+ ret AND dfs2(j)
- 반환
- 하나의 대기열 정의
- 연결 가능한 곳에 0을 삽입하고 q에 0을 삽입
- 동안(q는 비어 있지 않음) 다음을 수행합니다.
- 노드:=q의 첫 번째 요소
- q에서 요소 삭제
- 가장자리[노드]
- 의 각 i에 대해
- 연결할 수 없는 경우:
- 연결 가능한 위치에 i 삽입, q에 i 삽입
- from_cost :=from_cost 및 비용_from[노드]의 최소값
- 연결할 수 없는 경우:
- global_min :=cost_from의 최소 요소
- ret :=ret + from_cost - global_min
- 배열 위치 정의
- 0에서 n 사이의 i에 대해
- dfs(i)
- 배열 반전
- 포에 있는 각 i에 대해 다음을 수행합니다.
- 연결 가능한 경우:
- 다음 반복으로 이동
- 방문한 배열 지우기
- 초기:=dfs2(i)
- 이니셜이 참이면 다음을 수행합니다.
- 최고:=inf
- 방문한 각 j에 대해:
- best :=best와 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