글 읽기 - 전체 MST 를 구한후 최대간선 뺴면 틀렸다고 나오네요 ㅠㅠ

aza1200 4년 전 0

저같은 경우는 MST 의 값을 answer에 저장하면서 각각의 변들을 real 이라는 벡터에 집어넣었습니다.

그 이후에 real 이라는 vector 의 가장 마지막 값인 mst 의 가장 큰 간선을 뺴는 방식으로 답을 구했는데요

이것이 틀렸다고 나왔습니다

반면 제가 n-2 번쨰까지의 간선까지만 값을 구하고 mst 를 구하지는 않았더니 맞았다고 나왔습니다. 왜 이런 차이가 나는 것인가요??

#include<iostream>
#include<memory.h>
#include<vector>
#include<algorithm>

#define ll long long
using namespace std;


ll parent[100003];
ll N, M, from, to;
ll Cost;

struct load {
	ll from;
	ll to;
	ll Cost;
	load(ll a, ll b, ll c) : from(a), to(b), Cost(c) {}
};

bool operator<(load a, load b) {
	return a.Cost < b.Cost;
}

vector<load> vec;
vector<ll> real;

int find(int now) {
	if (now == parent[now]) return now;
	return parent[now] = find(parent[now]);
}

void Union(int a, int b) {
	a = find(a), b = find(b);
	if (a != b) parent[a] = b;
}
ll answer = 0;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= 100000; i++) parent[i] = i;
	while (M--) {
		cin >> from >> to >> Cost;
		vec.push_back(load(from, to, Cost));
	}
	sort(vec.begin(), vec.end());

	for (int i = 0; i < vec.size(); i++) {
		if (find(vec[i].from) != find(vec[i].to)) {
			Union(vec[i].from, vec[i].to);
			answer += vec[i].Cost;
			real.push_back(Cost);
		}
	}
	answer = answer - real[real.size() - 1];
	cout << answer << "\n";
}

aza1200 4년 전 0

아 제가 52번쨰 줄에 Cost 를 vec[i[.Cost 로 고치니까 답이 나오네요 ㅠㅠ 답변 안해주셔도 될거같습니다!

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

문제

문제

출처

ICPC

전체 MST 를 구한후 최대간선 뺴면 틀렸다고 나오네요 ㅠㅠ

aza1200 4년 전 0

aza1200 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말