[BOJ] 1833 고속철도 설계하기

문제

1833번: 고속철도 설계하기

N(1≤N≤200)개의 도시로 이루어진 나라가 있다. 이 도시들 사이를 다니는 고속철도망을 만들어 도시 간의 이동을 편하게 하려고 한다. 단, 고속철도망을 만든 후에 임의의 도시에서 다른 임의의 도시로 고속철도를 이용하여 이동할 수 있게 하려고 한다.

https://www.acmicpc.net/problem/1833

풀이

코드

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> pii;

struct info {
    int cost;
    int s, e;
};

int n;
int p[200];
vector<info> arr;
int ans = 0, tmp = 0;
vector<pii> pn;

int find(int a) {
    if (p[a] == -1) return a;
    return p[a] = find(p[a]);
}

void merge(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    p[b] = a;
}

int main() {
    memset(p, -1, sizeof(p));
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        for(int a, j = 0; j < n; j++) {
            scanf("%d", &a);
            if (i >= j) continue;
            if (a < 0) {
                ans += abs(a);
                if (find(i) != find(j)) merge(i, j);
            } else arr.push_back({a, i, j});
        }
    }
    sort(arr.begin(), arr.end(), [](info a, info b) {return a.cost < b.cost;});
    for(int i = 0; i < arr.size(); i++) {
        if (find(arr[i].s) == find(arr[i].e)) continue;
        tmp++;
        merge(arr[i].s, arr[i].e);
        ans += arr[i].cost;
        pn.push_back({arr[i].s, arr[i].e});
    }
    printf("%d %d\n", ans, tmp);
    for(pii i : pn) printf("%d %d\n", i.first+1, i.second+1);
}