[BOJ]백준 17490번: 일감호에 다리 놓기(C++)/MST

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

17490번: 일감호에 다리 놓기

간만에 제대로된(화나는) MST 문제

이렇게 호수 주변의 강의실(노드)들이 있고, 가운데에 와우동?이 있으며 각 강의실을 특정 개수의 돌멩이로 연결할 수 있을 때 K개 이하를 사용해서 모든 강의실이 연결될 수 있는지 묻는 문제

우선 이웃한 강의실 끼리는 공사중인 경로를 제외하고 기본적으로 모두 연결되어 있다

그렇기에 공사중인 경로가 1개 이하이면(0개이면 1~N까지의 강의실이 O 형태로 처음부터 연결되어있음, 1이어도 C의 형태로 연결되어 있음) 바로 YES를 출력하면 된다

그리고 특이한 건 입력으로 받는 K가 int 범위를 초과하기 때문에 입력받을 때 long long(C 기준)으로 받아줘야 한다

 

나는 공사중으로 입력되는 i, j가 무조건 i, i+1의 형태로 입력되는 줄 알아서 WA를 많이 받았다 😥

문제를 잘 읽자..... ㅜㅜ

#include <cstdio>
#include <vector>
#include <queue>
#define pii pair<int,int>
#define ull unsigned long long
#define INF 987654321
using namespace std;

int n, m;
ull k;
vector<vector<pii>> g;
vector<bool> c;

ull prim() {
	priority_queue<pii, vector<pii>, greater<>> pq;
	vector<int> cost(n + 2, 987654321);
	vector<bool> visit(n + 2, false);

	ull ans = 0;
	pq.push(make_pair(0, 0));
	cost[0] = 0;

	while (!pq.empty()) {
		int cur = pq.top().second; pq.pop();
		if (visit[cur])continue;

		visit[cur] = 1;
		for (auto x : g[cur])
			if (!visit[x.second] && (cost[x.second] > x.first)) {
				cost[x.second] = x.first;
				pq.push(make_pair(cost[x.second], x.second));
			}
	}

	for (int i = 1; i <= n; i++) {
		if (cost[i] == INF)return INF;
		else ans += cost[i];
	}
	return ans;
}

int main() {
	scanf("%d %d %lld", &n, &m, &k);
	c = vector<bool>(n + 1, true);
	g = vector<vector<pii>>(n + 1);

	for (int i = 1, s; i <= n; i++) {
		scanf("%d", &s);
		g[0].push_back(make_pair(s, i));
		g[i].push_back(make_pair(s, 0));
	}

	for (int i = 0, a, b; i < m; i++) {
		scanf("%d%d", &a, &b);
		if (b < a) {
			int temp = a;
			a = b;
			b = temp;
		}
		if (a == 1 && b == n) {
			c[b] = false;
		}
		else c[a] = false;
	}

	for (int i = 1; i <= n; i++)
		if (c[i]) {
			g[i].push_back(make_pair(0, (i == n) ? 1 : i + 1));
			g[(i == n) ? 1 : i + 1].push_back(make_pair(0, i));
		}

	if (m <= 1)printf("YES");
	else {
		auto ans = prim();
		if (ans <= k)printf("YES");
		else printf("NO");
	}
	return 0;
}