K. Sports Reporters

K.pdf

문제 설명에 의해 이벤트 $E_i$와 이벤트 $E_j$가 답이 요구하는 집합에 같이 있을 수 없는 조건은,

$s_i + d_i + t_{i,j} \leq s_j$ 또는 $s_j + d_j + t_{j,i} \leq s_i$

문제에 있는 조건 $t_{i,j} \leq t_{i,k} + t_{k,j}$ 에 의해서, 다음과 같은 정리가 성립한다.

$E_i$와 $E_j$가 같은 집합 안에 있을 수 없고, $E_j$와 $E_k$가 같은 집합 안에 있을 수 없으면, 항상 $E_i$와 $E_k$도 같은 집합 안에 있을 수 없다.

위 정리가 성립하므로, 이 문제를 이분 그래프의 Minimum Cut으로 해결할 수 있다.

우선, 이분 그래프의 왼쪽과 오른쪽에 각각 $n$개의 $E_i (1 \leq i \leq n)$ 들을 배치한다.

그리고 $s_i < s_j$ 이면서, $s_i + d_i + t_{i,j} \leq s_j$ 인 $i$, $j$에 대해 왼쪽 노드 $E_i$에서 오른쪽 노드 $E_j$로 가는 간선을 그어준다.

이 때 $n - 최대 매칭 값$이 문제에서 요구한 집합의 최대 크기가 된다.

집합에 들어가는 $E_i$들도 찾아야한다. 

매칭이 끝난 이분그래프(* 더 이상 source에서 sink로 확대 경로가 존재하지 않음) 안에서 source에 flood fill을 한다.

왼쪽 노드들에 대해서 색칠이 안된 $E_i$들은 집합안에 있을 수 없고, 오른쪽 노드들에 대해서 색칠이 된 $E_j$ 들도 집합 안에 있을 수 없다.

즉, $E_i$가 답이 요구한 집합안에 있기 위해서는 왼쪽 $E_i$는 색칠이 되어 있어야하고, 오른쪽 $E_i$에 대해서는 색칠이 안되어있어야한다.

K.cpp