[백준/BOJ] 백준 4792번 : 레드 블루 스패닝 트리

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

4792번: 레드 블루 스패닝 트리

k가 파란색 간선을 최소로 쓰는 스패닝 트리의 파란색 간선의 개수와 파란색 간선을 최대로 쓸 때 스패닝트리의 파란색 간선의 개수 사이라면 파란색 간선이 k개인 스패닝 트리를 만들 수 있다는 것을 이용하여(파란색 간선을 최소로 쓸 때와 최대로 쓸 때에서 간선을 바꿔가며 파란색 간선을 k개로 쓸 때를 만들 수 있을 때) 문제를 해결했다. 파란색 간선을 최소로 쓰는 스패닝 트리는 파란색 간선에 가중치를 두고 최소 스패닝 트리를 만들어서 구했고, 파란색 간선을 최대로 쓰는 스패닝 트리는 빨간색 간선에 가중치를 두고 최소 스패닝 트리를 만들어서 구했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

int n, m, k;
vector<int> output;
int min_blue, max_blue;
vector<pair<int, int>> blue_edge;
vector<pair<int, int>> red_edge;
vector<int> parent(1001);
vector<int> rank_size(1001);

void Pre1()
{
	min_blue = 0;
	max_blue = 0;
	blue_edge.clear();
	red_edge.clear();
}

void Pre2()
{
	for (int i = 1; i <= 1000; i++)
	{
		parent[i] = i;
		rank_size[i] = 1;
	}
}

int Find(int u)
{
	if (parent[u] == u)
		return u;

	return parent[u] = Find(parent[u]);
}

void Merge(int u, int v)
{
	u = Find(u);
	v = Find(v);

	if (rank_size[u] < rank_size[v])
	{
		parent[u] = v;
	}

	else
	{
		parent[v] = u;

		if (rank_size[u] == rank_size[v])
			rank_size[u]++;
	}
}

//파란색 간선을 최소 개수로 쓰는 스패닝 트리를 만들어본다
void MinBlueSolve()
{
	Pre2();

	vector<pair<int, pair<int, int>>> edge; //(가중치, (정점1, 정점2))

	//빨간색 간선은 가중치0, 파랑색 간선은 가중치1로 생각하고 최소 스패닝 트리를 만든다

	for (int i = 0; i < red_edge.size(); i++)
		edge.push_back(make_pair(0, red_edge[i]));
	for (int i = 0; i < blue_edge.size(); i++)
		edge.push_back(make_pair(1, blue_edge[i]));

	sort(edge.begin(), edge.end());

	int cnt = 0; //스패닝트리 간선 개수 
	for (int i = 0; i < edge.size(); i++)
	{
		int cost = edge[i].first;
		int u = edge[i].second.first;
		int v = edge[i].second.second;

		if (Find(u) != Find(v))
		{
			Merge(u, v);

			cnt++;

			//파란색 간선일때
			if (cost == 1)
				min_blue++;
		}

		//스패닝트리를 만들었을때
		if (cnt == n - 1)
			break;
	}
}

//파란색 간선을 최대 개수로 쓰는 스패닝 트리를 만들어본다
void MaxBlueSolve()
{
	Pre2();

	vector<pair<int, pair<int, int>>> edge; //(가중치, (정점1, 정점2))

	//빨간색 간선은 가중치1, 파랑색 간선은 가중치0으로 생각하고 최소 스패닝 트리를 만든다

	for (int i = 0; i < red_edge.size(); i++)
		edge.push_back(make_pair(1, red_edge[i]));
	for (int i = 0; i < blue_edge.size(); i++)
		edge.push_back(make_pair(0, blue_edge[i]));

	sort(edge.begin(), edge.end());

	int cnt = 0; //스패닝트리 간선 개수 
	for (int i = 0; i < edge.size(); i++)
	{
		int cost = edge[i].first;
		int u = edge[i].second.first;
		int v = edge[i].second.second;

		if (Find(u) != Find(v))
		{
			Merge(u, v);

			cnt++;

			//파란색 간선일때
			if (cost == 0)
				max_blue++;
		}

		//스패닝트리를 만들었을때
		if (cnt == n - 1)
			break;
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	while (1)
	{
		Pre1();

		cin >> n >> m >> k;

		if (n == 0 && m == 0 && k == 0)
			break;

		for (int i = 0; i < m; i++)
		{
			char c;
			int f, t;

			cin >> c >> f >> t;

			if (c == 'R')
			{
				red_edge.push_back(make_pair(f, t));
			}

			else
			{
				blue_edge.push_back(make_pair(f, t));
			}
		}

		//최소 스패닝 트리 자체를 만들 수 없을때
		if (m < n - 1)
		{
			output.push_back(0);
			continue;
		}

		//파란색 간선이 k개보다 적을때
		if (blue_edge.size() < k)
		{
			output.push_back(0);
			continue;
		}

		MinBlueSolve();
		MaxBlueSolve();

		//파란색 간선이 k개인 스패닝트리를 만들 수 있을때 
		//(파란색 간선을 최소로 쓸때와 최대로 쓸때에서 간선을 바꿔가며 파란색 간선을 k개로 쓸때를 만들 수 있을때)
		if (min_blue <= k && k <= max_blue)
			output.push_back(1);

		else
			output.push_back(0);
	}

	for (int i = 0; i < output.size(); i++)
		cout << output[i] << "\n";

	return 0;
}