백준 27498번 연애 혁명 [C++]

https://www.acmicpc.net/problem/27498

 

 

#문제 해결 방법

크루스칼 알고리즘을 사용하자

 

기존에 주어진 사랑 성사 관계는 

바뀌면 안되기 때문에 Union 함수로 이어주고

 

MST 를 최대 스패닝 트리로 만들어서 

연결되지 않고 남은 사랑 관계들을 

최소 값으로 만든다.

 

키 포인트를 정리하자면

1. 이미 연결된 사랑 관계는 스패닝트리에 미리 포함시킨다.

2.최대 스패닝 트리로 만들어서 남은 관계들의 값이 최소가 된게 한다.

 

로 요약 가능하다

 

 

#전체 코드

 

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

using namespace std;

const int MAX = 100001;

int parent[MAX];

int Find(int a) {
    if (parent[a] == a) return a;
    return parent[a] = Find(parent[a]); // 경로 압축 기법
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a != b) parent[b] = a; // 부모를 갱신하여 연결
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    vector<pair<int, pair<int, int>>> edges; // {weight, {u, v}}

    // 부모 초기화
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }


    for (int i = 0; i < M; i++) {
        int u, v, weight, d;
        cin >> u >> v >> weight >> d;

        if (d == 1) {
            Union(u, v);
        }
        else {
            edges.push_back({ weight, {u, v} });
        }
    }

    int total_weight = 0;

    // 간선을 가중치 기준으로 내림차순 정렬
    sort(edges.begin(), edges.end(), greater<pair<int, pair<int, int>>>());

    for (const auto& edge : edges) {
        int weight = edge.first;
        int u = edge.second.first;
        int v = edge.second.second;

        if (Find(u) != Find(v)) {
            Union(u, v);
        }
        else {
            total_weight += weight;
        }
    }

    cout << total_weight << "\n";

    return 0;
}