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

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

3176번: 도로 네트워크

 

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 <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

//노드, 최소, 최대를 담는 구조체
struct info
{
	int node, min, max;
};


int N, logN;
int* level;
info** sparse;
vector<pair<int, int>>* edges;	//<node, cost>

//노드별 레벨을 설정하는 함수
void set_level(int const& current)
{
	for (pair<int, int> 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<int, int>>[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<int, int> ans = { def_info.min, def_info.max };	//<min, 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\n", ans.first, ans.second);
	}

	for (int i = 0; i < N; i++) delete[] sparse[i];
	delete[] sparse;
	delete[] level;
	delete[] edges;
	return 0;
}

 

그 외

---