[백준] 13905 - 세부

https://www.acmicpc.net/problem/13905

13905번: 세부

 

어떤 하나의 가중치 연결 그래프가 주어지고 출발점에서 끝점까지 가는 경로 중, 지나가는 경로의 가중치 중 최솟값의 최대를 구하는 문제이다. 사실 말로만 하면 문제 이해가 어려울 수 있으니 문제를 직접 보는 것을 추천한다.

 

즉, 이러한 그래프에서 1 -> 5로가는 경로를 찾는다고 해보자.

1 -> 2 -> 3 -> 5

1 -> 7 -> 3 -> 5

1 -> 7 -> 5

1 -> 7 -> 6 -> 5

등 여러가지 경로가 있다. 하지만 각각의 경로의 가중치의 최솟값은 각각 2, 2, 1, 3이고, 그 중 최댓값은 1 -> 7 -> 6 -> 5(3)이다.

즉, 최단 경로와 상관없이 어떻게 돌아가던 가중치가 높은 경로를 돌아야 한다.

따라서 MST로 풀 수 있다. 사실 이 문제는 최소 스패닝 트리가 아니라 최대 스패닝 트리(?)인 것 같다.

 

M(aximum)ST를 구한 다음 dfs 또는 bfs로 그래프 탐색을 실시하면 된다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<vector<int>> v;
vector<vector<pair<int, int>>> map;
int parent[100001];
int Find(int x)
{
	if (parent[x] == x)
	{
		return x;
	}
	else
		return parent[x] = Find(parent[x]);
}
void Union(int a, int b)
{
	a = Find(a);
	b = Find(b);
	parent[a] = b;
}

int vis[100001];

void go(int node, int cost)
{
	for (auto &i : map[node])
	{
		int m = min(cost, i.second);
		if (vis[i.first] < m)
		{
			vis[i.first] = m;
			go(i.first, m);
		}
	}
}
bool compare(vector<int> &v1, vector<int> &v2)
{
	return v1[0] > v2[0];
}
int main()
{
	int n, m;
	cin >> n >> m;
	int a, b;
	cin >> a >> b;
	map.resize(n + 1);
	for (int i = 1; i <= n; i++)
	{
		parent[i] = i;
	}
	for (int i = 0; i < m; i++)
	{
		int c, d, e;
		cin >> c >> d >> e;
		vector<int> t = {e, c, d};
		v.push_back(t);
	}
	sort(v.begin(), v.end(), compare);
	for (auto &i : v)
	{
		if (Find(i[1]) != Find(i[2]))
		{
			Union(i[1], i[2]);
			map[i[1]].push_back({i[2], i[0]});
			map[i[2]].push_back({i[1], i[0]});
		}
	}
	vis[a] = 987654321;
	go(a, 987654321);

	cout << vis[b];
}