[BOJ] 2406 안정적인 네트워크

문제

2406번: 안정적인 네트워크

한 회사는 본사와 지사의 컴퓨터들을 연결하는 네트워크 시설을 보유하고 있다. 각 지사에는 네트워크용 컴퓨터가 한 대씩 있으며, 이들은 본사의 메인 컴퓨터와 직접 연결되어 있다. 몇몇 지사들끼리 연결되어 있는 경우도 있다.

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

풀이

코드

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

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

int n, m;
vector<info> adj;
vector<int> v[1000];
int p[1000], sm = 0;
vector<pii> ans;

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

void go() {
    for(int i = 0; i < adj.size(); i++) {
        if (find(adj[i].s) == find(adj[i].e)) continue;
        merge(adj[i].s, adj[i].e);
        ans.push_back({adj[i].s, adj[i].e});
        sm += adj[i].c;
    }
}

int main() {
    memset(p, -1, sizeof(p));
    scanf("%d %d", &n, &m);
    for(int a, b, i = 0; i < m; i++) {
        scanf("%d %d", &a, &b);
        a--; b--;
        v[a].push_back(b);
        v[b].push_back(a);
        if (find(a) == find(b)) continue;
        merge(a, b);
    }
    for(int i = 0; i < n; i++) {
        for(int a, j = 0; j < n; j++) {
            scanf("%d", &a);
            if (i >= j or i == 0 or j == 0) continue;
            adj.push_back({a, i, j});
        }
    }
    sort(adj.begin(), adj.end(), [](info a, info b) {return a.c < b.c;});
    go();
    printf("%d %d\n", sm, ans.size());
    for(pii i : ans) printf("%d %d\n", i.first+1, i.second+1);
}