글 읽기 - 알고리즘 질문입니다.

alohajihwan 7년 전 0

세부 문제를 처음에 최소 스패닝 트리(크루스칼 알고리즘)로 풀었습니다.

최대 간선을 하나씩 더해가며 그래프를 구성하고 S,E위치가 같은 그래프에 존재하면

값을 출력하였습니다. 이 알고리즘이 왜 잘못되었는지 알려주세요ㅠㅠ

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<queue>
#include<string>
#include<map>
#include<string.h>
#include<stack>
#include<fstream>
#include<set>
using namespace std;
#define ll long long
#define INF 987654321

int N, M;
//그룹 짓기
struct Disjoint {
	vector<int>parent,rank;

	Disjoint() {}
	Disjoint(int n) {
		parent.resize(n + 1, 0);
		rank.resize(n + 1, 1);
		for (int i = 1; i <= n; i++) parent[i] = i;
	}

	int Find(int u)
	{
		if (u == parent[u]) return u;
		return parent[u] = Find(parent[u]);
	}
	void merge(int u, int v)
	{
		u = Find(u);
		v = Find(v);
		if (u == v) return;
	//	if (rank[u] > rank[v]) swap(u, v);
		parent[u] = v;
	//	if (rank[u] == rank[v]) rank[v]++;
	}
};
vector<pair<int, int> >adj[100001];
int main()
{
	cin >> N >> M;	
	int s, e;
	cin >> s >> e;
	priority_queue<pair<int, pair<int,int> > > q;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		q.push(make_pair(c, make_pair(a, b)));	
	}
	Disjoint D(N);
	while (!q.empty()) {
		int c = q.top().first;
		int h1 = q.top().second.first;
		int h2 = q.top().second.second;
	
		q.pop();	
		if (D.Find(h1) == D.Find(h2)) continue;
		D.merge(h1, h2);
			
		if (D.Find(s) == D.Find(e)) {
			cout << c << endl;
			return 0;
		}
	}
}

jseo 7년 전 2

주어진 그래프가 연결되어 있지 않을수도 있어서, s 에서 d까지 도달을 못할수도 있습니다 (저도 이것 때문에 삽질좀 했습니다).

코드 맨 끝에 0 출력하는 코드 넣으니 AC 받네요.

alohajihwan 7년 전 0

와,,,,그러네요ㅠㅠㅠㅠㅠㅠㅠ 도달하지 못하는 경우가 있다는 것은 문제에 제시 해줬으면 좋았을 텐데..ㅠㅠㅠㅠㅠ

감사합니다! 덕분에 해결하였습니다ㅎㅎ

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

문제

문제

출처

ICPC

알고리즘 질문입니다.

alohajihwan 7년 전 0

jseo 7년 전 2

alohajihwan 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말