[Link Cut Tree] 7. Dinic Algorithm with LCT 먼저 알아야 할 것 : 디닉 알고리즘 Dinic 알고리즘은 유량이 흐르는 그래프에서 s에서 e로 흘릴 수 있는 최대 유량을 찾는 알고리즘으로,단순하게 구현할 경우 $O(V^2E)$의 복잡도를 가집니다.이 문제에서 차단 유량을 찾을 때 Link/Cut Tree를 이용하면 차단 유량을 $O(ElogV)$에 찾을 수 있고,알고리즘 전체는 $O(VElogV)$가 됩니다.차단 유량을 찾는 방법에 대해서만 설명하겠습니다. Link/Cut Tree에 구현되어 있어야 하는 기능-경로에서 비용이 최소인 간선(비용이 같으면 루트에 가까운 간선)-경로의 모든 간선에 비용을 더함-노드가 포함된 트리의 루트를 찾음-노드의 부모 노드를 찾음 Step 1) 흐를 수 있는 유량을 찾는 Step : findBlockFlow()x = .. 더보기 이전 1 ··· 11 12 13 14 15 16 17 ··· 24 다음 목록 더보기