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

(追記) (追記ここまで)

알고리즘 질문입니다.

13905번 - 세부

alohajihwan 9년 전 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 9년 전 2

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

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

alohajihwan 9년 전 0

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

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

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

알고리즘 질문입니다.

alohajihwan 9년 전 0

jseo 9년 전 2

alohajihwan 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말