BOJ 13091 Longest Shortest Path 풀이

학교에서 볼록최적화입문을 수강중이라 선형계획법 문제들을 풀고 있어서 풀이를 적습니다.
풀이 서술이 힘들어 디테일한 부분을 많이 생략하였습니다.

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

13091번: Longest Shortest Path

이 문제는 다음과 같은 LP로 표현 가능합니다.

$$ \mbox{maximize } d_t \\ \mbox{subject to }d_u\leq d_u+l_i+e_i \\d_s=0\\ \sum e_ic_i\leq P$$

듀얼을 취하면 다음과 같습니다.

$$ \mbox{minimize }y_1l_1+\cdots+y_ml_m+y_{m+1}P \\ \mbox{subject to } c_iy_{m+1}\geq y_i \mbox{    for    }1\leq i\leq m\\ y_{m+1}\geq \frac{1}{flow} $$

$f_i=\frac{y_i}{y_{m+1}}$ 이라 합시다. $f_i$는 $i$번 간선에 흐르는 유량을 나타냅니다.
그러면 $c_i\geq f_i$가 되어 $c_i$가 간선의 capacity가 됩니다.
우리가 알고싶은 것은 $y_{m+1}(l_1f_1+\cdots+l_mf_m+P)$의 최솟값입니다. $y_{m+1}\geq \frac{1}{flow}$이므로 $\frac{l_1f_1+\cdots+l_mf_m+P}{flow}$의 최솟값을 구하면 됩니다. 
유량을 고정시켜서 생각해보면 min cost로 흘리는 것이 유리합니다. min cost-max flow를 구할 때 최단거리가 변할 때마다 답을 갱신시켜주면 정답을 얻을 수 있습니다.

코드는 다음 링크에 있습니다.
http://boj.kr/94ca82eb665842d5926882672b8bb1e3