글 읽기 - 크루스칼로 시도했는데 50%에서 틀립니다. (TC 추가합니다)

kth990303 3년 전 11

크루스칼로 두 섬이 연결이 됐을 때, 그 때의 중량제한이 최대라 생각하여 아래와 같이 크루스칼 알고리즘을 이용했습니다.

적절한 반례를 생성해서 대입해봐도 이 코드를 저격하는 반례를 찾기 어렵네요.

반례나 로직에 틀린 점이 있다면 알려주시면 감사하겠습니다.

+) 맞왜틀 하시는 분들을 위해 테케를 추가합니다.

5 5
1 2 5
2 3 4
1 3 3
1 4 3
4 5 1
5 1
ans: 1

6 9
1 2 7
1 3 8
1 4 7
1 6 9
2 3 7
3 4 7
3 5 7
4 5 7
4 6 7
6 3
ans: 8

6 12
1 2 7
1 3 8
1 4 7
1 6 9
2 3 7
3 4 7
3 5 7
4 5 7
4 6 7
3 6 7
1 3 11
5 6 12
6 3
ans: 9

3 1
1 2 999999999
1 2
ans: 999999999

3 3
1 2 2
3 1 2
2 3 2
1 3
ans: 2

3 3
1 2 2
3 1 2
2 3 99999999
1 3
ans: 2




#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int MAX = 100001;
ll N, M, S, E, p[MAX], ans;
vector<pair<ll, pair<ll, ll>>> v;
ll find(ll a) {
	if (a == p[a])
		return a;
	return p[a] = find(p[a]);
}
bool merge(ll a, ll b) {
	a = find(a);
	b = find(b);
	if (a == b)
		return false;
	p[b] = a;
	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++) {
		p[i] = i;
	}
	for (int i = 0; i < M; i++) {
		ll a, b, cost;
		cin >> a >> b >> cost;
		v.push_back({ cost, {a,b} });
		v.push_back({ cost, {b,a} });
	}
	cin >> S >> E;
    // 중량제한이 큰 순서대로
	sort(v.rbegin(), v.rend());
	for (int i = 0; i < M; i++) {
		ll node1 = v[i].second.first;
		ll node2 = v[i].second.second;
		ll cost = v[i].first;
        // 연결이 안됐다면
		if (find(S) != find(E)) {
            // 연결시키고 그 때의 값을 ans로 바꿈.
			merge(node1, node2);
			ans = cost;
		}
        /*
        연결을 시키고 섬이 연결된 경우 ans로 처리해도 결과는 같았습니다.
        merge(node1, node2);
		if (find(S) == find(E)) {
			cout<<cost<<"\n";
			return 0;
		}
        */
	}
	cout << ans << "\n";
}

kth990303 3년 전 1

저는 바보였습니다...

40번째 줄에 M번만 진행하면 안되더군요. 양방향이니까 2*M인데...

도움받은 테케는 아래와 같습니다.

amenable_c 8달 전 1

정리해주신 테케 덕분에 도움 받고 갑니다.

6 12
1 2 7
1 3 8
1 4 7
1 6 9
2 3 7
3 4 7
3 5 7
4 5 7
4 6 7
3 6 7
1 3 11
5 6 12
6 3

크루스칼을 이용할 때 공장이 있는 도시 2개를 방문한 것만 체크하는 것이 아니라, 두 도시가 연결 되었는지 find()를 통해 검사 또한 진행했어야 했네요.

감사합니다.

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

문제

문제

출처

ICPC

크루스칼로 시도했는데 50%에서 틀립니다. (TC 추가합니다)

kth990303 3년 전 11

kth990303 3년 전 1

amenable_c 8달 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말