구사과

https://www.acmicpc.net/problem/6007 O(N^4)Maximum Toll Cost의 경우의 수가 O(N)이니. 이걸 고정시키고 O(N^3) Floyd Warshall을 돌리면 된다. Toll cost T보다 값이 크면 그 근처에 있는 에지들을 몽땅 날려버리고 플로이드. 반복 반복... 시간 복잡도는 O(N^4). TLE다. O(N^3)플로이드 와셜의 루프. For(i, j, k) dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);를 생각해 보자.맨 바깥쪽 루프에서 도는 것은 중간 경유지이다. 2차원 배열에 중간 경유지를 모두 돌면서 업데이트하는 것이다.그러면, 어떠한 j , k에 대해서, j -> k로 가는 최단 경로가, i까지 경..

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-18-shortest-paths-ii-bellman-ford-linear-programming-difference-constraints/30분 정도부터 보면 된다. 간략히 말하자면 변수 x1 ... xn N개와, xj - xi

https://en.wikipedia.org/wiki/Karger's_algorithm 그래프에서의 Minimum Cut은 그래프의 컴포넌트를 2개로 쪼개는 데 삭제해야 하는 간선의 개수를 뜻한다. (가중치를 붙여서 일반화한 경우도 있다. 지금 소개하는 알고리즘은 그 경우는 해결하지 못하는 걸로 알고 있음)이 중 정점 S와 T의 Minimum Cut을 구하는 것은 (즉, S와 T를 서로 다른 컴포넌트로 쪼개는 데 필요한 간선수) 알고리즘이 알려져 있다. (http://amugelab.tistory.com/entry/%EC%9C%A0%EB%9F%89-%EA%B4%80%EB%A0%A8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A0%95%EB%A6%AC) Minimum Cut의..