백준 20927번 Degree Bounded Minimum Spanning Tree

문제 요약

노드 갯수 N과 간선 갯수 M이 주어진다. 그리고 각 정점의 차수 제한 $b_i$가 주어진다.

차수 제한을 만족하는 스패닝트리 중에서 그 비용이 가장 작은 스패닝 트리를 출력하시오. 차수 제한을 만족하는 스패닝트리가 없다면 NO를 출력하라.

N은 최대 10, M은 최대 27이다.

풀이

일단 최대 입력으로 들어왔을 때, 간선을 고르는 경우의 수는 $\binom{27}{9}$로 500만이 조금 안된다.

여기에다가 $M$을 곱해도 시간 내에 들어온다. (스패닝 트리가 되려면 간선을 N-1개 골라야 한다.)

즉, 간선을 고르고 스패닝 트리인지 확인하기 위해서 BFS나 DFS를 해도 시간 내에 충분히 돈다.

BFS나 DFS는 $O(N+M)$이다.

#include<bits/stdc++.h>
using namespace std;
struct Edge {
    int u, v, w;
};
vector<vector<int>> G(15);
Edge a[30];
int N, M;
int b[15];
int deg[15];
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> M;
    for(int i=1;i<=N;++i) cin >> b[i];
    for(int i=0;i<M;++i) cin >> a[i].u >> a[i].v >> a[i].w;
    if(M < N - 1) {
        cout << "NO" << '\n';
        return 0;
    }
    vector<int> v(M, 0);
    for(int i=0;i<N-1;++i) v[i] = 1;
    int ans = 1e9;
    vector<int> ans_v;
    do {
        memset(deg, 0, sizeof(deg));
        for(int i=1;i<=N;++i) G[i].clear();
        int sum = 0;
        for(int i=0;i<M;++i) {
            if(!v[i]) continue;
            int u = a[i].u;
            int v = a[i].v;
            int w = a[i].w;
            deg[u]++; deg[v]++;
            G[u].push_back(v); G[v].push_back(u);
            sum += w;
        }
        bool valid = true;
        for(int i=1;i<=N;++i) valid &= deg[i] <= b[i];
        if(!valid) continue;
        queue<int> q;
        bool vis[15]; memset(vis, false, sizeof(vis));
        vis[1] = true; q.push(1);
        int cnt = 0;
        while(!q.empty()) {
            int cur = q.front();
            q.pop();
            ++cnt;
            for(int v : G[cur]) {
                if(vis[v]) continue;
                vis[v] = true;
                q.push(v);
            }
        }
        if(cnt == N) {
            if(ans > sum) {
                ans_v = v;
                ans = sum;
            }
        }
    } while(prev_permutation(v.begin(), v.end()));
    if(ans == 1e9) cout << "NO" << '\n';
    else {
        cout << "YES" << '\n';
        for(int i=0;i<M;++i) if(ans_v[i]) cout << a[i].u << ' ' << a[i].v << '\n';
    }
    return 0;
}