Problem Solving
-
BOJ 19934 Connecting SupertreesProblem Solving/Solution Sketch 2021. 2. 16. 20:09
Connecting Supertrees (IOI 2020 Day1 #2) 문제 설명 - $n$개의 정점이 있다. - 정점 $i$에서 정점 $j$로 가는 서로 다른 단순경로가 정확히 $p(i, j)$개가 되도록 그래프를 설계할 것이다. - 이를 만족하는 그래프가 존재하는지 판별하고, 존재한다면 그 중 하나를 구하여라. 존재성 판별 및 그래프 설계 일단, 조건을 만족하는 그래프가 존재하는지부터 생각해보자. 96점어치 Subtask에서는 $0 \leq p(i, j) \leq 2$이므로, $0 \leq p(i, j) \leq 2$일 때를 생각해보자. - $p(i, j) = 1$에 대한 관찰 Lemma 1. 정점 $i$에 대하여 $p(i, j) = 1$인 $j$들의 집합을 $S$라 하자. 그러면 $x, y \in..