7/26 연습

#1. 중량제한

문제 : icpc.me/1939

굉장히 다양한 풀이가 가능한 문제인데, description을 잘못 이해해서 ㅂㄷㅂㄷ하다가 결국 풀이를 까봤다.

1. BFS

물건을 보내는 공장을 $s$, 받는 공장을 $t$라고 하자.

또 각각의 정점까지 수송할 수 있는 최대의 비용을 $F[v]$라고 하자.

(정점 $v$, c=$s$에서 $v$까지 옮길 수 있는 최대 비용)의 순서쌍을 저장할 수 있는 큐 $Q$를 잡고, $Q$에 $(s,F[s]\leftarrow \infty)$를 넣으면서 BFS 개시.

$Q$가 빌 때까지, $Q$의 front $k$에 대해서 $k.v$에 연결되어 있는 점 $u$들을 보는데, $min(k.c,bridge\_capacity[v\to u])$가 기존의 $F[u]$보다 크다면 이 값으로 $F[u]$를 갱신해주고, $u,F[u]$를 $Q$에 넣으면 된다. 원하는 답은 $F[t]$.

Time Complexity : $O(BFS)=O(V+E)$

2. Kruskal Algorithm

문제를 잘 들여다보면, 결국 Minimum Spanning Tree에서 $s\to t$의 경로 상에서 bridge_capacity의 최댓값을 찾는 문제가 됨을 알 수 있다.

크루스칼 알고리즘을 돌릴 때처럼, 모든 에지를 bridge_capacity가 큰 순서대로 정렬하자. Union-Find를 이용하여 계속 점을 이어주면서, 어떤 에지 $e$를 추가했을 때 $s$와 $t$가 이어지면 $bridge\_capacity[e]$를 출력하면 된다.

Time Complexity : $O(E lg E + E\alpha (V)) = O(E lg E)$

얘가 왜 더 빠른지는 모르겠다. 입출력을 다르게 해서 그런가...

---

#2. 운동

문제 : icpc.me/1956

Floyd_Warshall 알고리즘으로 빠르게 답을 찾을 수 있다. 정점 $u$에서 $v$로 가는 최단경로의 길이를 $sp[u][v]$라고 하면, $sp[u][u]$의 최솟값을 출력하면 된다.

Time Complexity : $O(V^3)$

---