백준 1939: 중량제한

문제 요약

N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

문제 분류

• 자료 구조
• 그래프 이론
• 그래프 탐색
• 이분 탐색
• BFS
• 분리 집합

문제 풀이

[C++] 백준 11085: 군사 이동과 비슷한 문제이다. 간선을 가중치를 기준으로 내림차순 정렬시키고, 가장 가중치가 큰 간선부터 삽입해나가며 파악하면 된다. 어떤 간선을 삽입할 때 간선의 양 정점을 같은 집합으로 처리한다. 어떤 간선을 삽입해서 두 공장이 연결되었을 때, 해당 간선의 가중치가 최대의 가중치가 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int p[10001];

int find(int n) {
	if (p[n] == n) return n;
	p[n] = find(p[n]);
	return p[n];
}

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

int main()
{
	int n, m, in, in2, in3, res;
	multimap<int, pair<int, int>, greater<>> mm;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		scanf("%d%d%d", &in, &in2, &in3);
		mm.insert({ in3, {in,in2} });
	}
	for (int i = 0; i < n; i++)
		p[i] = i;
	scanf("%d%d", &in, &in2);
	auto iter = mm.begin();
	while (find(in) != find(in2)) {
		res = iter->first;
		merge(iter->second.first, iter->second.second);
		iter++;
	}
	cout << res;
}