백준 14621 나만 안되는 연애 혼내주기

 

 

 

심금을 울리는 제목...
경로에서 남-남 혹은 여-여 경로를 제외하고 크루스칼을 돌리고 연결된 노드의 수가 n과 같은지 확인하면 된다.
처음으로 유니온 파인드에서 갯수가 중요한 문제를 풀었는데 꽤 재미있다. 어렵게 내면 매우 어려울 수 있을듯.

 

 

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(v) v.begin(), v.end()

int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

vector<tuple<int, int, int> > adj;
int parent[1001];
bool isMale[1001];
int n, m;

void input() {
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) {
        char c; cin >> c;
        isMale[i] = c == 'M' ? true : false;
    }
    for(int i = 1; i <= m; ++i) {
        int a, b, c; cin >> a >> b >> c;
        if((isMale[a] && isMale[b]) || (!isMale[a] && !isMale[b])) continue;
        adj.emplace_back(c, a, b);
    }
}

int find(int u) {
    if(parent[u] < 0) return u;
    return parent[u] = find(parent[u]);
}

bool merge(int u, int v) {
    u = find(u); v = find(v);
    if(u == v) return false;
    if(parent[u] > parent[v]) swap(u, v); 
    parent[u] += parent[v];
    parent[v] = u;
    return true;
}

int main() {
    fastio;
    input();
    memset(parent, -1, sizeof(parent));
    sort(adj.begin(), adj.end());
    int ans = 0;
    for(auto& [c, u, v] : adj) {
        if(merge(u, v)) ans += c;
    }
    if(parent[find(1)] == -n) cout << ans;
    else cout << -1;
}