글 읽기 - 틀린 이유를 도저히 모르겠습니다

isyou7487 3년 전 0

간선들을 가중치순으로 오름차순 정렬 후 크루스칼 알고리즘으로 모든 간선들에 대해 연결 할지말지 선택후 MST를 구하는 코드입니다

초기에 발전소가 있는곳은 planted를 true로 만들어 주었고 발전소가 연결된 마을과 연결되지 않은 마을을 합쳐가면서 문제의 답을 구했는데

바로 틀렸다고 나오네요.. 예제포함 제가 생각해본 몇개의 tc도 다 답이 제대로 나오는데 어디가 문제일까요?

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long

using namespace std;

int N,M,K;
int parent[1001];
bool planted[1001];
vector<pair<ll, int> > linked[100001];
vector<pair<ll, pair<int, int> > > nodes;

int find(int u)
{
	if(parent[u] == 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(planted[u])
		parent[v] = u;
	else if(planted[v])
		parent[u] = v;
	else
		parent[v] = u;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin>>N>>M>>K;
	int x;
	for(int i=1; i<=K; i++)
	{
		cin>>x;
		planted[x] = true;
	}
	int a,b;
	ll c;
	for(int i=0; i<M; i++)
	{
		cin>>a>>b>>c;
		linked[a].push_back(make_pair(c,b));
	}
	for(int i=1; i<=N; i++)
	{
		parent[i] = i;
		for(int j=0; j<linked[i].size(); j++)
		{
			ll cost = linked[i][j].first;
			int v = linked[i][j].second;
			nodes.push_back(make_pair(cost, make_pair(i,v)));
		}
	}
	sort(nodes.begin(), nodes.end());
	ll ret = 0;
	for(int i=0; i<nodes.size(); i++)
	{
		ll cost = nodes[i].first;
		int u = find(nodes[i].second.first);
		int v = find(nodes[i].second.second);
		if(planted[u] && planted[v])
			continue;
		merge(nodes[i].second.first,nodes[i].second.second);
		ret += cost;
	}
	cout<<ret;
}

tizm423 3년 전 3

5 5 1
1
1 2 9
2 3 1
3 4 1
4 5 1
5 2 1

출력 : 13

맞는답 : 12

위 코드로 만들어지는 그래프는 MST가 아닙니다.

isyou7487 3년 전 1

감사합니다 양쪽 둘다 발전소에 연결되지 않았을때를 처리하지 못했네용

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

문제

문제

출처

ICPC

틀린 이유를 도저히 모르겠습니다

isyou7487 3년 전 0

tizm423 3년 전 3

isyou7487 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말