6135 - Cow Hurdles

여기를 클릭해 주세요.

문제 링크

---

 

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

 

 

문제 요약

---

 

\(N\)개의 정점으로 이루어진 가중치가 있는 방향 그래프가 주어 진다.

그 뒤 \(Q\)개의 쿼리가 주어지는데 각각의 쿼리마다 두 개의 수 \(u\), \(v\)가 주어진다. 각 쿼리에 대해서 구해야 하는 값은 아래와 같다.

 

\(u\), \(v\)로 가는 경로를 하나 선택했을 때 그 경로에 있는 엣지들의 무게들 중 가장 무거운 값이 있다고 하자.

이 값을 최소화 시키는 경로를 하나 찾는게 문제다. 실제 경로는 찾을 필요가 없고 최대중에 최소의 값만 찾으면 되기 때문에

쉽게 해결할 수 있다.

 

 

문제 풀이

 

 

 

 

---

 

 

\(D[u][v]\) = \(u\)에서 \(v\)로 가는 경로 중 만나는 엣지의 무게의 최대의 최소 라고 정의를 해 보자.

 

그렇다면 \(D[u][v]\) 를 어떻게 구할 수 있을지 생각을 해본다면 우리가 잘 알고 있는 \(Floyd\ Warshall\ Algorithm\)을 이용해 쉽게 해결할 수 있다는 생각이 든다.

\(u\)에서 \(v\)로 가는 경로 중 어떠한 경유지 \(k\)를 거쳐갈 때 우리는 한 문제가 두개의 부분문제로 나눠지는 것을 알 수 있다.

 

\(D[u][v]\ =\ \min_{\ 1 \leq\ k\ \leq\ n}(D[u][v],\ max(D[u][k],\ D[k][v]))\)

\(u\) - \(k\)의 경로의 값과 \(k\) - \(v\)경로의 값을 합치는 것은 위 수식으로 표현할 수 있다.

최대의 최소를 저장해야 하기 때문에 전체적으로는 최소값을 유지하지만 경로가 합쳐질때는 어쩔 수 없이 최대값을 선택해야 한다. 위와같은 방법으로 플로이드를 돌리면 각 쿼리에 대해서 \(O(1)\)에 구할 수 있다.

 

전체 시간복잡도는 \(O(N^3 + Q)\)이므로 충분히 시간에 들어온다.

 

 

 

소스 코드

 

 

 

 

---

 

#include <stdio.h> #include <algorithm>  using namespace std;  const int INF = 987654321; int n, m, q, u, v, w, D[310][310];  int main() {   scanf("%d%d%d", &n, &m, &q);   for (int i = 0 ; i < n ; ++i) {     for (int j = 0 ; j < n ; ++j) {       D[i][j] = (i == j) ? 0 : INF;     }   }   while (m--) {     scanf("%d%d%d", &u, &v, &w);     D[u - 1][v - 1] = min(D[u - 1][v - 1], w);   }      for (int k = 0 ; k < n ; ++k) {     for(int i = 0 ; i < n ; ++i) {       for (int j = 0 ; j < n ; ++j) {         D[i][j] = min(D[i][j], max(D[i][k], D[k][j]));       }     }   }      while (q--) {     scanf("%d%d", &u, &v);     printf("%d\n", D[u - 1][v - 1] == INF ? -1 : D[u - 1][v - 1]);   } }