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)\)

---