글 읽기 - 간선 끊어가기 문제 질문

Coxie 5년 전 0

다음과 같은 로직을 생각해 봤는데, 틀렸습니다가 뜹니다.

이미 비연결인 경우 0을 출력하고 종료한다. 1번 간선부터 dfs를 시작하여 모든 간선을 방문했는지 확인하는 방식으로 비연결인지 확인한다.
크루스칼 알고리즘을 이용하여 가중치 합이 최대인 트리를 만든다.

이 방법이 왜 틀렸을까요?

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int vlen, elen;
vector<tuple<int, int, int>> V1;
vector<int> V2[5555];
bool visit[5555];
void f(int n)
{
	if (visit[n]) return;
	visit[n] = 1;
	for (int nxt : V2[n])
		f(nxt);
}
int UF[5555];
int F(int a) { return UF[a] == a ? a : UF[a] = F(UF[a]); }
void U(int a, int b) { UF[F(a)] = F(b); }
int main()
{
	for (int i = 0; i < 5555; ++i) UF[i] = i;
	cin >> vlen >> elen;
	for (int i = 0, u, v, w; i < elen; ++i)
	{
		cin >> u >> v >> w;
		V1.push_back({ w,u,v });
		V2[u].push_back(v);
		V2[v].push_back(u);
	}
	f(1);
	for (int i = 1; i <= vlen; ++i)
	{
		if (!visit[i])
		{
			puts("0");
			return 0;
		}
	}
	sort(V1.rbegin(), V1.rend());
	int cnt = 0;
	int ans = 0;
	for (int i = 0; cnt != vlen - 1; ++i)
	{
		int w, u, v;
		tie(w, u, v) = V1[i];
		if (F(u) != F(v))
			U(u, v), ++cnt, ans += w;
	}
	cout << ans << '\n';
	return 0;
}

jh05013 5년 전 0

그래프 전체가 비연결이 되는 시점이 아니라 s와 t가 비연결이 되는 시점을 봐야 합니다.

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

문제

문제

출처

ICPC

간선 끊어가기 문제 질문

Coxie 5년 전 0

jh05013 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말