전형적인 Minimum cut 문제이다. 결국 문제에서 연결하라고 하는 대로 연결 하면 그래프가 나오고, 할 수 있는 것은 그 그래프에서 정점을 제거하는 것이다. 고로, 그래프에서 S / T를 제외한 최소 몇개의 정점을 제거해야 S - T로 가는 경로가 없는지를 구해야 한다.
Minimum cut 문제는 몇개의 간선을 제거하냐는 문제인데, 정점 제거 역시 쉽게 간선 제거로 환원할 수 있다. $in(i) -> out(i)$ 로 가는 유랑 1의 간선을 만들어주고, 간선은 끊지 못하게 ($\infty$ 유량) 을 주면 되기 때문이다. 옛날에 글로도 썼다. 시간 복잡도는 $O(N^2M^2)$.
숫자의 자리수를
고정시키고 생각해 보자. $A = a_0 a_1 a_2 a_3 \cdots a_{L-1}$ 이라고 하면, $A - rev(A)$ 를 정했다는 것은 $a_0 -
a_{L-1}, |a_1 - a_{L-2}|$ 에 들어갈 값을 정했다는 것을 의미한다. 대충 이걸 정하는 데 있어서 19^9 정도의
경우의 수가 있다. 각각의 값을 정하면, 그 값을 만드는 쌍의 개수는 쉽게 계산할 수 있다는 점을 유념하자.
이를
최적화하는 것은 잘 알려진 meet in the middle을 사용하는데, 19^5 정도의 경우의 수를 백트래킹으로
다 나열한 후 정렬을 통해서 $A_i + A_j = D$ 인 쌍의 $Sum(B_i * B_j)$ 를 계산해 주면 그냥 해결할 수 있다.
그래프가 DAG이기 때문에, 위상 정렬을 할 수 있다. 위상 정렬 상의 정점 $x$의 순서를 $top(x)$ 라 하자.
각 정점 $v$에 대해서, 해당 정점으로 들어오는 간선들도 있고, 나가는 간선들도 있을 것이다. $x → v$로 들어오는 간선 중 $top(x)$의 최댓값을 $L(v)$라 하고, $v → x$ 로 나가는 간선 중 $top(x)$의 최솟값을 $R(v)$라 하자. 만약 간선이 없어 최대 / 최솟값이 정의가 되지 않을 경우 $0, n+1$을 매긴다.
$L(v), R(v)$ 값을 통해서 확실히 알 수 있는 것은, 위상 정렬 번호가 $[L(v)+1,top(v)-1], [top(v)+1,R(v)-1]$ 구간에 있는 정점들은 $v$에서 도달할 수 없다는 것이다. 이를 $v$에서 "거른" 정점이라 하자. 모든 정점 $v$에 대해서 걸러진 정점을 합집합한 후 후보에서 제외한다면, 전부는 아니더라도 Critical Project가 될 수 없는 일부 정점들을 추려낼 수 있을 것이다.
여기서 매우 놀라운 사실은, 이렇게만 정점들을 걸러내도 남은 정점들이 모두 Critical Project가 된다는 것이다. 이 사실은 위상 정렬을 어떻게 하느냐와는 아무 상관이 없다. 위상 정렬이 올바르기만 하면 위 사실이 항상 성립한다.
이에 대한 증명은 의외로 간단하다. Critical Project들은 모두 남은 정점에 속하니, Critical Project가 아닌 정점들은 위 과정에서 걸러진다는 사실을 증명하면 된다. 어떠한 Critical Project가 아닌 정점 $v$와, $v$에서 오갈 수 없는 정점들 중 $top(u) < top(v)$인 $u$가 존재한다고 하자. 우리는 이 때 $v$를 구간 안에 포함하는 정점이 존재함을 증명할 것이다. $top(u) < top(v)$이며, $u$에서 $v$로 갈 수 없는 정점들 중 $top(u)$를 최대화하는 $u$가 존재하니, 이를 생각해 보자.
* $top(v) < R(u)$ 일 때는 이 u가 v를 거르기에 증명이 종료된다.
* 그렇지 않다면, $top(u) < R(u) < top(v)$이니 가정에 의해 $R(u)$에 해당하는 정점에서 $v$로 가는 경로가 있어야 한다. 그러면 $u - R(u) - v$로 가는 경로가 있으니 가정에 모순이다
고로, $top(u) < top(v)$이며 $u$에서 $v$로 갈 수 있는 경로가 없는 정점 $u$가 하나 이상 존재한다면, $v$가 걸러짐을 증명할 수 있다. 동일하게, $top(u) > top(v)$이며 $v$에서 $u$로 갈 수 있는 경로가 없는 정점 $u$가 하나 이상 존재한다면, $v$는 걸러짐을 보일 수 있다. 이제 변홧값 배열을 통해서 구간의 합집합을 구하면, Critical Project를 찾을 수 있다.
