Boj1939_중량제한

Published: by Creative Commons Licence

  • Bfs + 이분탐색을 통해 문제를 해결하였다.
#include<iostream>
#include<vector>
#include<queue>
#include<set>
using namespace std;

int n, m, a, b, c, factory1, factory2, l = 1, r;
vector<vector<pair<int, int> > > adj;
vector<vector<int> > temp;
set<pair<int, int> > s;
queue<int> q;
int visit[10010];

bool isconnected() {
	bool res = false;
	q.push(factory1);
	while (!q.empty()) {
		int nownode = q.front();
		if (nownode == factory2) {
			res = true;
			break;
		}
		q.pop();
		for (int i = 0; i < temp[nownode].size(); i++) {
			if (!visit[temp[nownode][i]]) {
				q.push(temp[nownode][i]);
				visit[temp[nownode][i]] = 1;
			}
		}
	}
	for (int i = 0; i < 10010; i++) visit[i] = 0;
	while (!q.empty()) q.pop();
	return res;
}

int main() {
	scanf("%d %d", &n, &m);
	adj.resize(n + 1);

	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		adj[a].push_back({ b,c });
		adj[b].push_back({ a,c });
		r = r < c ? c : r;
	}
	scanf("%d %d", &factory1, &factory2);

	//binary search
	while (l <= r) {
		temp.clear();
		s.clear();
		temp.resize(n + 1);
		int mid = (l + r) / 2;
		for (int i = 1; i < adj.size(); i++) {
			for (int j = 0; j < adj[i].size(); j++) {
				if (mid <= adj[i][j].second) {
					int node1 = min(i,adj[i][j].first), node2 = max(i,adj[i][j].first);
		
					if (s.find({ node1,node2 })==s.end()) {
						s.insert({ node1,node2 });
						temp[node1].push_back(node2);
						temp[node2].push_back(node1);
					}
				}
			}
		}
		if (isconnected()) l = mid + 1;
		else r = mid - 1;
	}
	printf("%d", r);

}

다른 사람의 코드를 보니 중량이 가장 큰 다리부터 내림차순으로 하나씩 union 해가면서 공장을 확인하면 Union-find로 문제를 해결할 수 있다.

union-find 코드

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

int n, m, a, b, c, U, V, parent[100010];
typedef pair<int, pair<int, int> > ipii;
vector<ipii> list;

int find(int num) {
	if (parent[num] == num) return num;
	else return parent[num] = find(parent[num]);
}
void merge(int num1, int num2) {
	int pnode1 = find(num1);
	int pnode2 = find(num2);
	parent[pnode1] = pnode2;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) parent[i] = i;
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		list.push_back({ -c,{b,a} });
	}
	scanf("%d %d", &U, &V);

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

	for (int i = 0; i < list.size(); i++) {
		int node1 = list[i].second.first, node2 = list[i].second.second;
		merge(node1, node2);
		if (find(U) == find(V)) {
			printf("%d", -list[i].first);
			break;
		}
	}

}