[일반] 이 문제 정당성 증명 어케함?

[익명(211.185)]

1647 도시 분할 계획 https://www.acmicpc.net/problem/1647

Baekjoon Online Judge

최소 스패닝 트리 만들고 제일 긴 엣지 빼면 정답인거 이해는 가는데

몬가 엄밀하게 보이고 싶음

귀류법으로 더 좋은해 있다고 가정하고 모순 끌어내려고 해봤는데 잘안댐..

피붕이 도움점 ㅠㅠ

[익명(211.173)]

크루스칼에 간선 추가하는 시행을 n-1번 대신 n-2번 한다고 생각하면 됨

[익명(119.206)]

간선추가 n-1번 시행시 연결그래프임이 보장됨을 전제로 깔고 간다면 쉬움