티스토리 뷰

ICPC/2012 대전

K. Sports Reporters

전명우 2013.10.19 00:30


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


'ICPC > 2012 대전' 카테고리의 다른 글

F. Pandora  (0) 2013.10.19
L. Square Annulus  (0) 2013.10.19
K. Sports Reporters  (4) 2013.10.19
댓글
  • 프로필사진 lsc4719 Ei와 Ej가 같은 집합 안에 있을 수 없고, Ej와 Ek가 같은 집합 안에 있을 수 없으면, 항상 Ei와 Ek도 같은 집합 안에 있을 수 없다. => 이 문제를 이분 그래프의 Minimum Cut으로 해결할 수 있다.
    어째서 그런건가요??
    2015.10.27 22:28 신고
  • 프로필사진 noeffserv 안녕하세요? 궁금한게 있습니다. "Ei와 Ej가 같은 집합 안에 있을 수 없고, Ej와 Ek가 같은 집합 안에 있을 수 없으면, 항상 Ei와 Ek도 같은 집합 안에 있을 수 없다." 저는 이 정리를 보고 아래처럼 정리했습니다. "Ei와 Ej가 동시에 취재가능하고, Ej와 Ek가 동시 취재 가능하면, 항상 Ei와 Ek도 동시에 취재가능하다." 만약 이게 맞다면 아래 데이터에서 조금 이상한 부분이 생기는데요.
    3
    10 15 20
    4 3 10
    0 4 6
    0 2
    0
    여기서 i=1,j=3,k=2로 뒀을때,
    S[1] + d[1] + t[1][3] <= S[3] 를 만족하므로 1과 3은 동시에 취재 가능하고,
    S[2] + d[2] + t[2][3] <= S[3] 을 만족하므로 2와 3이 동시에 취재가능하므로,
    1과 2는 동시에 취재가능하다. 이런식으로 전개를 하게되는데요.

    그런데 1과 2는 동시에 취재가 불가능합니다.
    S[1] + d[1] + t[1][2] <= S[2]
    10 + 4 + 4 <= 15
    를 만족시키지 않기 때문이죠.

    그래서 이상하게 생각했습니다. 무엇이 잘못된건지 잘 모르겠네요. 답변 해주시면 감사하겠습니다!
    2016.10.04 08:22 신고
  • 프로필사진 전명우 문제를 다룬지 오래되어서 새로 읽어보았는데, 말씀하신 부분이 이상합니다.

    Ei와 Ej가 답이 말하는 집합에 같이 있을 수 없다라는 것은, Ei와 Ej가 한 기자에게 취재되지 못하는 경우를 말합니다.

    때문에, "Ei와 Ej가 같은 집합 안에 있을 수 없고, Ej와 Ek가 같은 집합 안에 있을 수 없으면, 항상 Ei와 Ek도 같은 집합 안에 있을 수 없다." 이 명제가 "Ei와 Ej가 동시에 취재가능하고, Ej와 Ek가 동시 취재 가능하면, 항상 Ei와 Ek도 동시에 취재가능하다." 이렇게 바뀔 수가 없죠.
    2016.10.04 09:20 신고
  • 프로필사진 noeffserv 아.. 저는 "답이 말하는 집합" 이라고 이해했네요.. 그래서 반대로 생각하게 된것 같습니다. 답변 감사합니다. 2016.10.04 09:31 신고
댓글쓰기 폼