백준4792 레드 블루 스패닝 트리

작성일 | In

문제 링크

  • http://icpc.me/4792

사용 알고리즘

  • MST

시간복잡도

  • O(M log M)

풀이

파란 간선을 최소로 사용해서 만든 Spanning Tree에서 파란 간선의 개수를 MinBlue, 최대로 사용했을 때의 개수를 MaxBlue라고 하면, MinBlue <= K <= MaxBlue가 만족할 때 1 아니면 0입니다.

MinBlue는 빨간 간선의 가중치를 0, 파란 간선의 가중치를 1로 설정한 다음에 MST를 돌리면 되고, MaxBlue는 반대로 파란 간선의 가중치를 0으로 하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;

int par[1010];
int find(int v){
	if(v == par[v]) return v;
	return par[v] = find(par[v]);
}
int merge(int u, int v){
	u = find(u), v = find(v);
	if(u == v) return 0;
	par[u] = v;
	return 1;
}

struct edge{
	char color;
	int s, e;
	edge(){}
	edge(char x, int y, int z) : color(x), s(y), e(z) {}
};

vector<edge> v;

bool redFirstSort(edge &a, edge &b){
	return a.color > b.color;
}

bool blueFirstSort(edge &a, edge &b){
	return a.color < b.color;
}

int mst(int n){
	int cnt = 0, ret = 0;
	for(int i=0; i<=n; i++) par[i] = i;
	for(int i=0; i<v.size(); i++){
		if(merge(v[i].s, v[i].e)){
			if(v[i].color == 'B') ret++;
			cnt++;
		}
		if(cnt == n-1) break;
	}
	return ret;
}

void f(int n, int m, int k){
	v.clear();
	for(int i=0; i<m; i++){
		char c; int s, e;
		cin >> c >> s >> e;
		v.push_back({c, s, e});
	}
	int a, b;
	sort(v.begin(), v.end(), redFirstSort);
	a = mst(n);
	sort(v.begin(), v.end(), blueFirstSort);
	b = mst(n);
	if(a <= k && k <= b) cout << "1\n";
	else cout << "0\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	while(1){
		int n, m, k; cin >> n >> m >> k;
		if(!n && !m && !k) break;
		f(n, m, k);
	}
}