MST 게임 (feat. 백준, 16202번)

MST 게임
https://www.acmicpc.net/problem/16202

16202번: MST 게임

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
bool visit[1001]{false};
vector<tuple<int, int, bool>> arr[1001];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
void find(int& value, int& next){
    value = 999999999;
    for(auto& v : arr)
        for(auto& p : v)
            if(get<2>(p) && get<1>(p) < value)
                value = get<1>(p), next = get<0>(p);
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, M, K;
    cin >> N >> M >> K;
    for(register int m = 1, a, b; m <= M; ++m)
        cin >> a >> b, arr[a].push_back(make_tuple(b, m, true)), arr[b].push_back(make_tuple(a, m, true));
    for(register int k = 0, t, mv, sv = 1; k < K; ++k){
        t = 0;
        memset(visit, false, N + 1);
        q.push(make_pair(0, sv));
        while(!q.empty()){
            auto next = q.top().second, cost = q.top().first; q.pop();
            if(visit[next])
                continue;
            visit[next] = true;
            t += cost;
            for(auto& v : arr[next]){
                auto nnext = get<0>(v);
                cost = get<1>(v);
                if(!visit[nnext] && get<2>(v))
                    q.push(make_pair(cost, nnext));
            }
        }
        bool check = true;
        for(int n = 1; n <= N; ++n)
            if(!visit[n]){
                check = false;
                break;
            }
        if(check)
            cout << t << ' ';
        else
            cout << 0 << ' ';
        find(mv, sv);
        for(auto& p1 : arr)
            for(auto& p2 : p1)
                if(get<1>(p2) == mv)
                    get<2>(p2) = false;
    }
	return 0;
}
// *&)*@*

 

반응형

최소 스패닝 트리를 구하는 문제입니다.

저는 프림 알고리즘을 사용하여 풀이하였습니다.

효율적이진 못하지만 기존의 MST처럼 next, cost의 pair 형태가 아니라 next, cost, bool의 tuple 형태로 구성했습니다.

MST가 구해지면 cost가 가장 작은 항목들에 대해서 tuple의 bool을 false로 치환하여 다음 MST를 풀이했습니다.