[BOJ/Gold 3] 백준 27498 연애 혁명(C++)

문제 링크

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

27498번: 연애 혁명

 

 

문제

신촌고등학교 학생회장 기령이는 최근 학생들의 복잡한 사랑관계로 인해 고민이 많다. 학생들이 공부에 집중하지 못해 전반적인 성적이 하락하고 있는 것이다. 이에 기령이는 학생들의 복잡한 마음을 덜어주기 위해 일부의 사랑 관계를 강제로 포기하게 만드는 특단의 조치를 취하기로 했다. 단, 파장을 최소화 하기 위해 다음의 조건을 만족하도록 조치할 것이다.

• 사랑 관계 중, 이미 성사된 사랑 관계는 포기하도록 하지 않는다.
• 사랑 관계가 K각 관계를 이루지 않도록 한다. K(K ≥ 3)각 관계라는 것은 임의의 서로 다른 K명의 학생 A1, A2, ⋯, Ai, ⋯, AK에 대하여, i ≠ 1인 모든 i에 대해서 Ai−1과 Ai사이에 사랑 관계가 존재하며, AK와 A1사이에 사랑 관계가 존재하는 것을 의미한다.
• 포기하도록 만들 수 있는 경우가 여러가지일 경우 포기하도록 만든 애정도의 합을 최소화한다.

다만 학생의 수가 매우 많아 이러한 조건을 만족하는 경우를 찾기는 어렵다. 조건을 만족하도록 사랑관계를 포기하게 했을 때, 포기하도록 만든 애정도의 합의 최솟값을 구해보자.

입력

첫째 줄에 학생의 수 N(3 ≤ N ≤ 10,000), 사랑 관계의 수 M(N ≤ M ≤ 100,000)가 주어진다.

이후 M개의 줄에 걸쳐 사랑관계를 표현하는 세 개의 정수 ai, bi, ci와 성사 여부 di가 공백으로 구분되어 주어진다. (1 ≤ ai < bi ≤ N; 1 ≤ ci ≤ 10,000)

이는 학생 ai와 bi가 애정도가 ci인 사랑관계에 있으며 di가 1일 경우 이미 성사된 사랑 관계임을, 0일 경우 그렇지 않음을 의미한다.

주어지는 데이터는 임의의 두 학생이 한 개 이상의 사랑 관계에 걸쳐 연결되며, 동일한 두 학생 간의 사랑 관계가 여러 번 주어지지 않는다. 또한 성사된 사랑 관계만으로 이루어진 K각 관계는 존재하지 않는다.

출력

포기하도록 만든 애정도의 합의 최솟값을 출력한다.

예제 입력 1

5 7
1 3 10 0
2 4 7 0
1 2 6 0
1 5 8 0
2 5 13 1
3 4 2 1
4 5 6 0

예제 출력 1

19

예제 입력 2

4 6
1 2 4 0
1 4 1 0
3 4 2 0
2 3 5 0
1 3 6 0
2 4 3 0

예제 출력 2

7

알고리즘 분류

• 크루스칼 알고리즘

풀이

이미 성사된 사랑 관계라면 같은 집합으로 묶어준다.

이루어지지 않은 관계들끼리 애정도를 기준으로 내림차순하고 최소 스패닝 트리를 구성한다.

최소 스패닝 트리에 포함되지 않은 관계들의 총합이 정답이 된다.

이루어지지 않은 관계들의 애정도의 합을 먼저 구하고 최소 스패닝 트리에 포함된 관계들의 애정도의 총합을 뺀 것이 포기하도록 만든 애정도의 총합이 된다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 10001
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct INFO {
    int S, E, C;
};

int N, M, A, B, C, D;
vector<INFO> Edge;
int Parent[MAX];
int Sum, Answer;

void init() {
    for (int i = 0; i < MAX; i++) {
        Parent[i] = i;
    }
}

int find(int Now) {
    if (Parent[Now] == Now) {
        return Now;
    }
    return Parent[Now] = find(Parent[Now]);
}

void union_Group(int X, int Y) {
    int PX = find(X);
    int PY = find(Y);
    if (PX < PY) {
        Parent[PY] = PX;
    }
    else {
        Parent[PX] = PY;
    }
}

bool Comp(INFO A, INFO B) {
    return (A.K > B.K);
}

void input() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> A >> B >> C >> D;
        if (D == 0) {
            Edge.push_back({ A,B,C });
            Sum += C;
        }
        else {
            union_Group(A, B);
        }
    }
}

void settings() {
    sort(Edge.begin(), Edge.end(), Comp);
    for (int i = 0; i < Edge.size(); i++) {
        int Start = Edge[i].S;
        int End = Edge[i].E;
        int Cost = Edge[i].C;
        if (find(Start) != find(End)) {
            union_Group(Start, End);
            Answer += Cost;
        }
    }
}

void find_Answer() {
    cout << Sum - Answer << "\n";
}

int main() {
    FASTIO
    init();
    input();
    settings();
    find_Answer();

    return 0;
}