[C++] 도시 분할 계획

[문제]

1647번: 도시 분할 계획 (acmicpc.net)

1647번: 도시 분할 계획

[문제 풀이]

크루스칼 알고리즘을 이용해서 쉽게 풀리는 문제이다.

크루스칼 알고리즘을 사용하고 제일 긴 간선의 가중치를 제거하면 완성!

[회고]

처음에 틀려서 어디가 이상한가 했는데 알고보니 양방향 그래프라서 m보다 더 많이 진행을 했는데 크루스칼 알고리즘에서 간선만큼 돌려야하는데 m만큼 돌려서 틀렸었다. 사소한것에 주의를 하자.

[코드]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int,pair<int,int> > > graph;
int parent[100001];
int n,m;
int answer;

int find(int x){
    if(parent[x] == x){
        return x;
    }
    return parent[x] = find(parent[x]);
}

void mergeUnion(int x, int y){
    int a = find(x);
    int b = find(y);
    if(a == b){
        return;
    }
    parent[b] = a;
    return;
}

bool sameParent(int x, int y){
    if(find(x) == find(y)){
        return true;
    }
    return false;
}

void solve(){

    int max_answer = 0;

    for(int i = 0;i<graph.size();i++){
        if(sameParent(graph[i].second.first,graph[i].second.second) == false){
            mergeUnion(graph[i].second.first,graph[i].second.second);
            max_answer = max(max_answer,graph[i].first);
            answer += graph[i].first;
        }
    }
    answer -= max_answer;

    return;
}

int main(){
    cin>>n>>m;
    for(int i = 0;i<m;i++){
        int source,destination,cost;
        cin>>source>>destination>>cost;
        graph.push_back(make_pair(cost,make_pair(source,destination)));
        graph.push_back(make_pair(cost,make_pair(destination,source)));
    }

    for(int i = 0;i<=n;i++){
        parent[i] = i;
    }
    sort(graph.begin(),graph.end());

    solve();

    cout<<answer<<endl;
    return 0;
}