글 읽기 - 유니온파인드 이용 42%에서 틀리는데 어디가 문젤까요?

kth990303 2년 전 0

크루스칼 알고리즘을 이용한 MST로 접근해보았습니다.

이 때, 현재 차수>=제한차수일 경우 간선 연결하지 못하도록 하였습니다.

또한, 간선 번호가 작은 것부터 출력해야 하므로 간선 정보를 입력받는 부분에서 57번째 줄에 swap 또한 해주었습니다.

42%에서 틀리는데 문제점을 딱히 찾기가 힘들더군요... 알고리즘이 잘못된 것일까요?

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <cmath>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int MAX = 11;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int N, M, d[MAX], in[MAX], p[MAX];
vector<pair<int, pi>> v;
vector<pi> ans;
// 유니온 파인드
int find(int a) {
	if (a == p[a])
		return a;
	return p[a] = find(p[a]);
}
bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)
		return false;
	if (a > b)
		swap(a, b);
	p[b] = a;
	return true;
}
// 모든 정점이 연결됐는지 확인하는 함수
bool check() {
	for (int i = 2; i <= N; i++) {
		if (find(i) != find(1))
			return false;
	}
	return true;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> d[i];
		p[i] = i;
	}
	while (M--) {
		int a, b, cost;
		cin >> a >> b >> cost;
		if (a > b)
			swap(a, b);
		v.push_back({ cost, {a,b} });
	}
	sort(all(v));
	for (auto i : v) {
		int n1 = i.second.first;
		int n2 = i.second.second;
		int cost = i.first;
        // 현재차수가 제한차수보다 크거나 같으면 연결할 수 없으므로 continue
		if (in[n1] >= d[n1] || in[n2] >= d[n2])
			continue;
        // 연결이 안됐으면 연결
		if (find(n1) != find(n2)) {
			merge(n1, n2);
            // 현재차수 증가
			in[n1]++; in[n2]++;
			ans.push_back({ n1, n2 });
		}
        // 만약 모든 정점이 연결됐다면
		if (check()) {
			cout << "YES\n";
			for (auto j : ans) {
				cout << j.first << " " << j.second << "\n";
			}
			return 0;
		}
	}
	if (check())
		cout << "YES\n";
	else
		cout << "NO\n";
}

kth990303 2년 전 0

아래 반례에서 모든 경우를 탐색하지 않는군요 ㅠㅠ

12
2 1 2 2 2 2
2 8
4 4
7 1
4 55
7 10
3 7
6 3
7 21
6 30
5 4
5 50
5 100

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

문제

문제

출처

ICPC

유니온파인드 이용 42%에서 틀리는데 어디가 문젤까요?

kth990303 2년 전 0

kth990303 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말