티스토리 뷰

IOI/IOI2014

[IOI2014 Day2] Friend 해법

전명우 2014. 7. 18. 06:02

이 문제에서 독특한 성질의 그래프가 주어진다. 답으로 어떤 노드 집합을 구해야하는데, 이 노드 집합에 있는 각 노드는 서로 연결되어 있지 않으며, 각 노드별로 주어진 특성값의 합이 최대가 되어야한다.


아직 이 문제의 정해를 찾지 못 했다. 우선 69점 받는 방법을 설명하겠다.


부분 문제1) 노드가 많아야 10개이므로 각 노드에 대해서 집합에 포함되는지 포함되지 않는지 구하는 경우의 수는 노드의 개수가 $n$개라 할 때, $2^n$개이다. $2^n$가지에 대해 모두 가능한 집합인지 확인하고, 최대값을 갱신하면 된다.


부분 문제2) 입력으로 주어지는 그래프에 간선이 존재하지 않는다. 따라서, 모든 노드의 값을 더해주면 된다.


부분 문제3) 입력으로 주어지는 그래프는 완전그래프다. 따라서, 노드의 값들 중 최대값을 구하면 된다.


부분 문제4) 입력으로 주어지는 그래프는 트리이다. 이 문제는 DP(Dynamic Programming, 동적계획법)으로 해결할 수 있다. 우선, 0번을 루트로한 rooted tree를 만들어준다. 다이나믹 배열의 정의는 아래와 같다.


$D[i]=$노드 $i$의 서브 트리에 대해서 노드 $i$가 집합에 포함될 때 가능한 최대값

$E[i]=$노드 $i$의 서브 트리에 대해서 노드 $i$가 집합에 포함되지 않을 때 가능한 최대값


점화식은 아래와 같다.

$D[i] = \sum\limits_{k} E[k]$

$E[i] = \sum\limits_{k} \max(D[k],E[k])$

(여기서, $k$는 노드 $i$의 자식노드들)


최종적으로 답은 $\max(D[0],E[0])$이 된다.


부분 문제5) 입력으로 주어지는 그래프는 이분 그래프이다. 따라서, 그래프에서 vertex cover를 구하여 $n$에서 뺀 값을 구하면 된다. 이에 대한 자세한 설명은 생략한다.



전체 풀이) 공식 풀이(영문). 번역 된 풀이는 나중에 여유가 되면 적겠습니다..



'IOI > IOI2014' 카테고리의 다른 글

[IOI2014 Day2] Holiday 해법  (0) 2015.07.31
[IOI2014 Day2] Gondola 해법  (0) 2014.07.17
IOI2014 Day 2 종료  (0) 2014.07.17
[IOI2014 Day1] Rail 해법  (0) 2014.07.17
[IOI2014 Day1] Game 해법  (3) 2014.07.17
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함