백준 21924 도시 건설 혼내주기

 

무난한 mst 문제

인데... 모든 건물이 연결되어있는 경우는 parent의 값으로 판별하려고 코드 수정하다가 삽질했다... 
원인은 pu pv의 부모값 비교하는 곳에서 swap을 안하고 pu에 pv값만 넣고 있었다...........

사람들이 ps 안하다가 다시 하면 재활이라고 하는데 진짜 정확한 표현인듯.

 

#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};

struct state {
    int u, v, d;
    state(int uu, int vv, int dd) {
        u = uu, v = vv, d = dd;
    } 
};

vector<state> adj;
int parent[100005];
ll tot = 0;
int n, m;

void input() {
    cin >> n >> m;    
    for(int i = 0; i < m; ++i) {
        int a, b, c; cin >> a >> b >> c;
        adj.push_back(state(a, b, c));
        tot += c;
    }
}

bool comp(const state& a, const state& b) {
    return a.d < b.d;
}

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

int main() {
    fastio;
    input();

    memset(parent, -1, sizeof(parent));

    sort(adj.begin(), adj.end(), comp);
    ll ans = 0;
    
    for(int i = 0; i < m; ++i) {
        auto [u, v, d] = adj[i];
        int pu = find(u), pv = find(v);
        if(pu == pv) continue;
        
        if(parent[pu] > parent[pv]) swap(pu, pv);
        parent[pu] += parent[pv];
        parent[pv] = pu;

        ans += d;
    }

    if(parent[find(1)] == -n) cout << tot - ans;
    else cout << -1;

    return 0;
}