📝 문제 정보#
🧐 관찰 및 접근#
- 파란색 간선을 $k$개, 빨간색 간선을 $(N-1) - k$개 이용해서 MST를 짜야하는데..
- 일단 파란색 간선 $k$개를 결정하면 빨간색은 그냥 유파를 다해버리면 되니까, 파란색 간선을 잘 고르는게 중요하다.
- 나이브하게 한다면 $\binom{\binom{N}{2}}{k}$인가? 간선 개수는 그렇다 쳐도, $k$개를 고르는게 너무 큰디…
- 작은 문제부터 차근히 풀어보자.
- $k = 0$
- 이라면 모든 간선들로 스패닝트리가 만들어지는지 확인하는 문제로 바뀐다.
- $k = 1$
- ![[Drawing 2026-01-30 19.56.46.excalidraw.png]]
- 위와 같은 그래프가 있었다고 생각하자.
- 파란 간선 1개를 $1 - 2$ 같은걸 골라버리면 불가능해지는 문제가 생긴다. 잘 골라야 한다.
- 음.. 빨간색으로 미리 다 합쳐놓고, 나머지를 연결할 개수 이상의 파란간선은 필요한거 같은데..
- 그런데, 이미 MST가 잘 있다면, 빨간 간선을 파란 간선으로 대체하는게 꽤 자유로운가? 이것만 되면 큰 문제가 없는데?
- $k > 1$
- ![[Drawing 2026-01-30 20.04.04.excalidraw.png]]
- 주황색이 이미 만들어진 MST, 나머지를 남은 간선이라고 하자.
- 어떤 파란색 간선을 하나 쓰고싶으면, 두 정점으로 가는 경로에 있는 빨간색을 끊어버리고 파란색으로 새로 연결하면 된다!
- 이게 안되는 경우는 이미 그 두 정점으로 가는 경로가 다 파란색 간선만으로 연결된 경우인데..
- 아하, 분리집합을 하나 더 관리하는걸로 쉽게 풀 수 있는 것 같다.
💻 풀이#
- 코드 (C++):
void solve(){
while(1){
int N, M, K; cin >> N >> M >> K;
if(N + M + K == 0) break;
vector<pii> Redges, Bedges;
rep(i, 0, M){
char color; cin >> color;
int u, v; cin >> u >> v;
u--; v--;
if(color == 'R') Redges.push_back({u, v});
else Bedges.push_back({u, v});
}
UnionFind UF(N), BUF(N);
// 일단 파란색 간선을 최소로 쓸때 되는지 확인
int cnt = 0;
for(auto [u, v]: Redges) UF.merge(u, v);
for(auto [u, v]: Bedges) if(UF.merge(u, v)){
cnt++;
BUF.merge(u, v);
}
if(cnt > K){
cout << 0 << '\n';
continue;
}
// 빨간 간선을 하나하나 파란색으로 바꾸기
for(auto [u, v]: Bedges) if(BUF.merge(u, v)) cnt++;
if(cnt < K){
cout << 0 << '\n';
continue;
}
cout << 1 << '\n';
}
}