호지

최소 스패닝 트리를 알고 있으면 쉽게 풀 수 있는 문제이다. 두 집 사이에 경로가 있으면 길을 없앨 수 있고, 유지비용을 최소로 하도록 도시를 분할한다. 따라서, 최소 스패닝 트리를 구한 후, 최대의 유지비용이 드는 경로를 없애면 유지비용이 최소인 도시 분할 방법을 구할 수 있다. #include #include #include using namespace std; vector edge; vector parent; int find_root(int x){ if(parent[x] == x) return x; else return parent[x] = find_root(parent[x]); } void union_root(int x, int y){ x = find_root(x); y = find_root(y)..