BOJ 6497 전력난

1 개요[ | ]

BOJ 6497 전력난

2 C++[ | ]

#include <bits/stdc++.h>
using namespace std;

int m, n, sumDist;
typedef pair<int, int> Road;
vector<Road> v[200001];
bool visited[200001];

struct compare {
    bool operator()(Road a, Road b) {
        return a.second > b.second;
    }
};

void solve() {
    int answer = sumDist;
    memset(visited, 0, sizeof(visited));
    priority_queue<Road, vector<Road>, compare> pq;
    visited[0] = true;
    for (int i=0; i<v[0].size(); i++) pq.push(v[0][i]);
    while (!pq.empty()) {
        Road x = pq.top();
        pq.pop();
        if (visited[x.first]) continue;
        visited[x.first] = true;
        answer -= x.second;
        for (const auto& nx: v[x.first]) {
            if(visited[nx.first]) continue;
            pq.push(nx);
        }
    }
    cout << answer << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while (true) {
        cin >> m >> n;
        if (m == 0 && n == 0) break;
        for (int i=0; i<m; i++) {
            v[i].clear();
        }
        sumDist = 0;
        int x, y, z;
        for(int i=0; i<n; i++) {
            cin >> x >> y >> z;
            v[x].push_back({y, z});
            v[y].push_back({x, z});
            sumDist += z;
        }
        solve();
    }
}

#include <bits/stdc++.h>
using namespace std;

int m, n;
vector<tuple<int, int, int>> v;
int parent[200000];

int Find(int x) {
    if(x == parent[x]) return x;
    return parent[x] = Find(parent[x]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if(a < b) {
        parent[b] = a;
    } else {
        parent[a] = b;
    }
}

void solve() {
    sort(v.begin(), v.end());
    for (int i=0; i<m; i++) {
        parent[i] = i;
    }
    int answer = 0;
    for (auto [z, x, y]: v) {
        x = Find(x);
        y = Find(y);
        if (x == y) {
            answer += z;
            continue;
        }
        Union(x, y);
    }
    cout << answer << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while (true) {
        cin >> m >> n;
        if (m == 0 && n == 0) break;
        v.clear();
        int x, y, z;
        for (int i=0; i<n; i++) {
            cin >> x >> y >> z;
            v.push_back({z, x, y});
        }
        solve();
    }
}