Erdos & Gallai
Problem Solving/Algorithm notes 2008. 3. 4. 02:08
최근에 UVa 모의고사를 참여했는데.. 문제가 비교적 쉬워서 3문제를 풀고..
마지막으로 D번을 풀려고했는데.. 문제가 도저히 이해가 안되서.. 그냥 포기하고 잤다..
문제는 11414 - Dream 인데.. 그냥 까먹고 있다가..
최근에 10720 - Graph Construction 문제를 우연히 보고나서.. 이게 같은문제란걸 파악.. -_-;;
문제 description을 어떻게 저렇게 엉망으로 써놓을수가 있는지.. 참내.. 내가 영어를 못하는건가.. 흑.. ㅠ_ㅠ;
이 문제는 Erdos & Gallai Theorem으로 해결할 수 있는데..
vertex의 개수와 각 vertex의 degree가 주어지고.. 이를 만족하는 simple graph를 그릴수 있는지 묻는 문제..
여기서의 simple graph는 undirect이고 self edge가 없고 같은 pair의 vertex를 연결하는 edge는 최대 하나이어야 한다..
참고자료:
'Problem Solving > Algorithm notes' 카테고리의 다른 글
Ellipse (타원) (0) | 2009.04.15 |
---|---|
Combination 개수 구하기 (Pascal's Triangle) (2) | 2009.02.07 |
Number of Swap Operations (0) | 2008.07.24 |
소수 구하는 방법 (Sieve of Eratosthenes) (2) | 2008.07.15 |
Horner's Rule (0) | 2008.05.04 |
GCD SUM (0) | 2008.03.18 |
Misère Nim (2) | 2007.12.16 |
BSP Tree (0) | 2007.08.28 |
Catalan Number (10) | 2007.08.12 |
Multinomial Theorem (0) | 2007.08.04 |