백준 14621 나만 안되는 연애

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

14621번: 나만 안되는 연애

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

using namespace std;

int parent[1001];

int findParent(int k){
    return parent[k] == k ? k : parent[k] = findParent(parent[k]);
}

void mg(int a, int b){

    int pa = findParent(a);
    int pb = findParent(b);

    if (pa < pb) {
        parent[pb] = pa;
    }
    else if (pa > pb) {
        parent[pa] = pb;
    }

}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    int ans = 0, cnt = 0;

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    vector<char> sex(n + 1);
    vector<pair<int, pair<int, int>>> dist(m + 1);

    for (int i = 1; i <= n; i++) {
        cin >> sex[i];
    }

    for (int i = 1; i <= m; i++) {
        cin >> dist[i].second.first >> dist[i].second.second >> dist[i].first;
    }

    sort(dist.begin(), dist.end());

    for (int i = 1; i <= m; i++) {
        if (cnt == n - 1) {
            break;
        }

        int d = dist[i].first;
        int u = dist[i].second.first;
        int v = dist[i].second.second;

        if (findParent(u) != findParent(v) && sex[u] != sex[v]) {
            mg(u, v);
            cnt++;
            ans += d;
        }


    }

    if (cnt != n - 1) {
        cout << -1;
    } else {
        cout << ans;
    }


    return 0;
}

 

간단한 mst 문제로, 크루스칼 알고리즘으로 구현하였다.

edge를 dist 오름차순으로 정렬하고, 각 edge에 대하여 연결 시 cycle이 생성되지 않으면 해당 경로를 그린다.

다만 이 경로에는

1. 사심 경로는 사용자들의 사심을 만족시키기 위해 남초 대학교와 여초 대학교들을 연결하는 도로로만 이루어져 있다.

라는 조건이 붙어있다. edge를 연결할 때 두 대학 사이의 성별을 비교하여 해결할 수 있다.