목록최소 신장 트리 (1)

넘치게 채우기

[BOJ] 1647 - 도시 분할 계획

https://www.acmicpc.net/problem/1647BOJ - 도시 분할 계획문제 유형: 최소 신장 트리문제 난이도: Gold IV시간 제한: 2초메모리 제한: 256MB 문제동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 임의의 두 집 사이에 경로가 항상 존재한다.마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된..
PS/BOJ 2024. 12. 23. 11:47
이전 Prev 1 Next 다음