[BOJ] 백준 1647 도시 분할 계획

문제 링크

www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

 

풀이

1) 문제에서 설명하는 조건은 각 분리된 마을이 최소 스패닝 트리여야 한다는 말입니다.

2) 우선 전체 마을에 대해 최소 스패닝 트리를 만들어주고, 그 트리에서 코스트가 가장 큰 간선을 제거해주면 1)을 만족하며 마을이 두 구역으로 분리됩니다.

 

 

정답 코드

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
#define ft first
#define sd second
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vb = vector<bool>;
using vs = vector<string>;
using vd = vector<double>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vvpii = vector<vpii>;

struct Edge {
    int u, v, cost;

    Edge(int u = 0, int v = 0, int c = 0) : u(u), v(v), cost(c) {}
};

int n, m;
int par[111'111];
vector<Edge> p;

int find(int v) {
    if (par[v] == -1) return v;
    return par[v] = find(par[v]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(par, -1, sizeof(par));
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        p.emplace_back(u, v, c);
    }
    sort(all(p), [&](const auto &a, const auto &b) {
        return a.cost < b.cost;
    });
    int ans = 0;
    int last = 0;
    for (auto e: p) {
        auto[u, v, c] = e;
        u = find(u);
        v = find(v);
        if (u != v) {
            par[u] = v;
            ans += c;
            last = c;
        }
    }
    cout << ans - last;

}