[BAE/<JOON> 문제풀이] 1647. 도시 분할 계획

폭풍저그머성찡 2021. 4. 17. 13:15

www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집

www.acmicpc.net

주어진 간선으로 MST를 구성하고 그 간선내의 가장 큰 간산 하나를 제거하면 정답을 얻을 수 있다

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

using namespace std;

struct h { int x, y, v; };

bool cmp(h a, h b) { return a.v < b.v; }

int parent[100001];

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

int main() {
    int n, m; cin >> n >> m; 
    vector<h> arr(m + 1); int totalp = 0;
    for (int i = 1; i <= m; i++) { 
        cin >> arr[i].x >> arr[i].y >> arr[i].v; 
        totalp += arr[i].v; 
    }

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

    sort(arr.begin(), arr.end(), cmp);

    int cv = 0;
    int pn = 1;
    int sum = 0;
    int mx = -2100000000;
    while (true) {
        int p1 = findp(arr[pn].x);
        int p2 = findp(arr[pn].y);
        if (p1 != p2) {
            sum += arr[pn].v;
            mx = mx > arr[pn].v ? mx : arr[pn].v;
            cv++;
            parent[p2] = p1;
        }
        if (cv == n - 1) break;
        pn++;
    }

    cout << sum - mx;

    return 0;
}