[백준] 4792 - 레드 블루 스패닝 트리 (c++)

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

 

문제 요약

무방향, 무가중치, 연결 그래프가 주어진다. 간선은 빨간색 혹은 파란색으로 칠해져 있다. 파란색 간선이 정확히 k개인 스패닝 트리를 만들 수 있는지 구해라

 

풀이 (M)

• MST

스패닝 트리를 구성하는데 필요한 파란색 간선의 최소 개수를 mn 최대 개수를 mx라고 할 때 mn<=k<=mx면 참이다. 증명을 해보자.

최소 파란 간선을 고정시키고 크루스칼을 돌려도 결과에 영향을 주지 않는다. 최소 파란 간선을 고정시킨 상태로 최대 파란 간선 스패닝 트리를 구성한다.

최소 파란 간선 스패닝 트리에서 최대 파란 간선 중 하나를 삽입하고 생긴 사이클의 간선 하나를 삭제한다. 스패닝 트리엔 사이클이 없기 때문에 파란 간선은 삭제되지 않는다.

최소 파란 간선 스패닝 트리에서 빨간 간선을 하나씩 대체하며 파란색 간선을 mn~mx개 쓴 스패닝 트리를 모두 만들 수 있다.

#include<bits/stdc++.h>
using namespace std;

int n, m, k;
deque<tuple<int,int,char>> edge;

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

void Init() {
    edge.clear();
    fill(p, p + 1001, 0);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    while (1) {
        Init();
        cin >> n >> m >> k;
        if (n == 0)
            return 0;
        for (int i = 0; i < m; i++) {
            int u, v; char c;
            cin >> c >> u >> v;
            if (c == 'R')
                edge.push_front({ u,v,c });
            else
                edge.push_back({ u,v,c });
        }

        int cnt=0, mn = 0,mx=0;
        for (auto e : edge) {
            int a, b;char c; tie(a, b,c) = e;
            if (find(a)!= find(b)) {
                cnt++;
                if(c=='B')
                    mn++;
                Union(a, b);
                if (cnt == n-1)
                    break;
            }
        }
        reverse(edge.begin(),edge.end());
        cnt=0; fill(p, p + 1001, 0);
        for (auto e : edge) {
            int a, b;char c; tie(a, b,c) = e;
            if (find(a)!= find(b)) {
                cnt++;
                if(c=='B')
                    mx++;
                Union(a, b);
                if (cnt == n-1)
                    break;
            }
        }
        if(cnt<n-1)
            cout << 0 <<'\n';
        else
            cout << (mn<=k&&k<=mx) <<'\n';
    }
}