[BOJ] 20927 Degree Bounded Minimum Spanning Tree

(2021년 2월 24일에 작성한 글입니다)

 

20927번: Degree Bounded Minimum Spanning Tree

N, M 크기가 작아서 Brute Force인가? 생각했지만

일단 원래 MST 방법대로 구함

WA

​

그래서 Brute Force로 짰다

근데 시간초과 났어

그래서 일단 미뤄두고 있다가

효규가 맞왜틀이라고 해서 코드 봤는데

비트마스킹으로 했더라

우왕

​

효규가

모든 노드가 하나 이상의 간선과 연결되어 있고

전체 간선 개수가 N-1이면 트리이지 않느냐고 했는데

나도 처음엔 맞는 줄 알았는데 아니었다

이건 완전 그래프일때만 성립하는거야!

그래서 Union-Find나 BFS로 트리인지를 확인해야 한다

나는 Union-Find로 했다.

#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ = 666, inf = 1e18, mod = 1e9 + 7;
ll n, m, x, y, t, k, u, h, a, b, c, d, z, temp, r, rr;
ll A[n_], B[n_];
vector<PP>v;
vector<P>ans;
vector<int> par;
int getPar(int a) {
    if (par[a] == -1) return a;
    return par[a] = getPar(par[a]);
}
void merge(int a, int b) {
    a = getPar(a); b = getPar(b);
    if (a != b) par[a] = b;
}
void f(ll x, ll sum, ll bit, ll r) { //x는 확인중인 간선, r은 포함한 간선 개수
    if (x == m) {
        if (r != n - 1) return;
        for (int i = 1; i <= n; i++)if (A[i] < B[i] || !B[i]) return;
        if (sum >= d) return;

        par.clear(); par.resize(n + 1, -1);
        for (int i = 0; i < m; i++) {
            if (bit & (ll)1 << i) {
                merge(v[i].second.first, v[i].second.second);
            }
        }

        for (int i = 1; i <= n; i++) {
            if (getPar(i) != getPar(1)) return;
        }

        temp = bit;
        d = sum;

        return;
    }
    B[v[x].second.first]++, B[v[x].second.second]++;
    f(x + 1, sum + v[x].first, bit | ((ll)1 << x), r + 1);
    B[v[x].second.first]--, B[v[x].second.second]--;
    f(x + 1, sum, bit, r);
}
void solve() {
    cin >> n >> m;
    if (n == 1) {
        cout << "YES" << '\n';
        return;
    }

    for (int i = 1; i <= n; i++)cin >> A[i];
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        v.push_back({ c,{a,b} });
    }
    d = inf;
    f(0, 0, 0, 0);
    if (d == inf) {
        cout << "NO";
        return;
    }
    for (ll i = 0; i < 28; i++)if (temp & ((ll)1 << i))ans.push_back({ v[i].second.first,v[i].second.second });
    cout << "YES" << '\n';
    for (int i = 0; i < ans.size(); i++)cout << ans[i].first << ' ' << ans[i].second << '\n';
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    //cin >> t;
    t = 1;
    while (t--)solve();
    return 0;
}

아.. 코드 스타일이 낯설어서 보니까 이건 전반적으로 효규가 작성했다.

여기서 트리인지 확인하는 부분만 내가 짰다.