[C++]백준 - 3176번 문제

[C++]백준 - 3176번 문제

3176번: 도로 네트워크 (acmicpc.net)

3176번 : 도로 네트워크

N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다.

모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다.

총 K개의 도시 쌍이 주어진다. 이때, 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000)

다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양의 정수이다.

다음 줄에는 K가 주어진다. (1 ≤ K ≤ 100,000)

다음 K개 줄에는 서로 다른 두 자연수 D와 E가 주어진다. D와 E를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구해서 출력하면 된다.

출력

총 K개 줄에 D와 E를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력한다.

생각해 볼 점

LCA 문제입니다.

기본적인 풀이 방법은 11438번 문제와 동일합니다.

다만, 여기서는 공통 조상을 찾으면서, 최댓값과 최솟값을 같이 찾아줘야 합니다.

그냥 조상을 찾는 테이블에서, 최솟값, 최댓값도 같이 비교해서 저장해주면 금방 풀립니다.

코드

#include #include #include #include using namespace std; //노드, 최소, 최대를 담는 구조체 struct info { int node, min, max; }; int N, logN; int* level; info** sparse; vector>* edges; // //노드별 레벨을 설정하는 함수 void set_level(int const& current) { for (pair next_node : edges[current]) { if (level[next_node.first] == -1) { level[next_node.first] = level[current] + 1; sparse[next_node.first][0] = info{ current, next_node.second, next_node.second }; set_level(next_node.first); } } } //스파스 테이블을 만드는 함수 void set_sparse() { for (int log_lv = 0; log_lv < logN; log_lv++) { for (int i = 0; i < N; i++) { info prev_info = sparse[i][log_lv]; if (prev_info.node != -1) { prev_info = sparse[prev_info.node][log_lv]; sparse[i][log_lv + 1] = info{ prev_info.node, min(prev_info.min, sparse[i][log_lv].min), max(prev_info.max, sparse[i][log_lv].max) }; } } } } int main() { //기본값 상수 const info def_info = info{ -1, 1000000, 0 }; scanf("%d", &N;); logN = log2(N) + 1; //binary lifting level = new int[N]; sparse = new info * [N]; edges = new vector < pair>[N]; //입력, 에지 생성 for (int i = 0; i < N - 1; i++) { int a, b, c; scanf("%d %d %d", &a;, &b;, &c;); a--; b--; edges[a].push_back({ b, c }); edges[b].push_back({ a, c }); level[i + 1] = -1; sparse[i] = new info[logN]; fill_n(sparse[i], logN, def_info); } sparse[N - 1] = new info[logN]; fill_n(sparse[N - 1], logN, def_info); level[0] = 0; set_level(0); set_sparse(); int K; scanf("%d", &K;); while(K--) { int a, b; scanf("%d %d", &a;, &b;); a--; b--; //swap if (level[b] < level[a]) { int temp = a; a = b; b = temp; } int lv_diff = level[b] - level[a]; pair ans = { def_info.min, def_info.max }; // //B의 레벨을 A와 동일 레벨로 올림 while (lv_diff) { int log_lv = log2(lv_diff); lv_diff -= 1 << log_lv; ans = { min(ans.first, sparse[b][log_lv].min), max(ans.second, sparse[b][log_lv].max) }; b = sparse[b][log_lv].node; } //공통 조상찾기 & 최소 최대 갱신 while (a != b) { int log_lv = log2(level[a]); for (; 0 < log_lv; log_lv--) { if (sparse[a][log_lv].node != sparse[b][log_lv].node) break; } ans = { min(ans.first, min(sparse[a][log_lv].min, sparse[b][log_lv].min)), max(ans.second, max(sparse[a][log_lv].max, sparse[b][log_lv].max)) }; a = sparse[a][log_lv].node; b = sparse[b][log_lv].node; } printf("%d %d

", ans.first, ans.second); } for (int i = 0; i < N; i++) delete[] sparse[i]; delete[] sparse; delete[] level; delete[] edges; return 0; }

그 외

from http://popoli31.tistory.com/201 by ccl(A) rewrite - 2021-12-19 17:26:55