글 읽기 - 반례가 뭐가 있을까요?

vegatrash 4년 전 0

데이터가 10000개 같은것만 빼고는 왠만한 경우 다 대입해본거 같은데

도저히 못찾겠어요....

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <unordered_set>
#include <queue>
#include <algorithm>
#define MAX_SIZE 10002

using namespace std;

int n, m, money;
int root[MAX_SIZE];
int _rank[MAX_SIZE];
vector<int> fCost;

void rootInit(int tree[]) {
	for (int i = 0; i < MAX_SIZE; i++) {
		tree[i] = i;
	}
}

int find(int x) {
	if (root[x] == x) {
		return x;
	}
	else {
		// "경로 압축(Path Compression)"
		// find 하면서 만난 모든 값의 부모 노드를 root로 만든다.
		return root[x] = find(root[x]);
	}
}

void Union(int x, int y) {
	x = find(x);
	y = find(y);

	// 두 값의 root가 같으면(이미 같은 트리) 합치지 않는다.
	if (x == y)
		return;

	// "union-by-rank 최적화"
	// 항상 높이가 더 낮은 트리를 높이가 높은 트리 밑에 넣는다. 즉, 높이가 더 높은 쪽을 root로 삼음
	if (_rank[x] < _rank[y]) {
		root[x] = y; // x의 root를 y로 변경
	}
	else {
		root[y] = x; // y의 root를 x로 변경

		if (_rank[x] == _rank[y])
			_rank[x]++; // 만약 높이가 같다면 합친 후 (x의 높이 + 1)
	}
}

int main() {
	cin >> n >> m >> money;
	rootInit(root);

	fCost.push_back(0);
	for (int i = 0; i < n; i++) {
		int cost;
		cin >> cost;
		fCost.push_back(cost);
	}
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		Union(a, b);
	}

	

	int payment = 0;
	vector<int> minCostRoot(MAX_SIZE); // 어떤 집단의 최소 비용을 저장할 벡터. 예를들어 minCostRoot[3]의 값은 3이 포함된 집단에서 최소비용이다.
	fill(minCostRoot.begin(), minCostRoot.end(), 1e9);
	for (int i = 1; i <= n; i++) {
		if (fCost[i] < minCostRoot[root[i]]) {
			minCostRoot[root[i]] = fCost[i];
		}
	}

	for (int i = 0; i < MAX_SIZE; i++) {
		if (minCostRoot[i] < 1e9) {
			payment += minCostRoot[i];
		}
	}
	if (money >= payment) {
		cout << payment;
	}
	else {
		cout << "Oh no";
	}

	return 0;
}

vegatrash 4년 전 0

75번 줄 주석 수정합니다.

3이 포함된 집단이 아니라 3이 루트인 Set의 최소 비용이라는 말이에요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례가 뭐가 있을까요?

vegatrash 4년 전 0

vegatrash 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말