호지

최소 스패닝 트리를 알고 있으면 쉽게 풀 수 있는 문제이다. 두 집 사이에 경로가 있으면 길을 없앨 수 있고, 유지비용을 최소로 하도록 도시를 분할한다. 따라서, 최소 스패닝 트리를 구한 후, 최대의 유지비용이 드는 경로를 없애면 유지비용이 최소인 도시 분할 방법을 구할 수 있다. #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)..

최소 스패닝 트리 문제를 크루스칼 알고리즘을 적용하여 풀었다. find_root는 연결된 최상위 노드를 찾는 함수이다. union_root는 연결할 2개의 노드가 최상위노드가 다르면 같게 바꿔주는 함수이다. 간선과 가중치에 대한 정보를 edge vector에 저장하고 가중치 기준으로 sort한 후, edge벡터를 탐색함으로 가중치가 최소인 최소스패닝트리를 구할 수 있다.(그리디 알고리즘) #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..