글 읽기 - 13418번 반례 혹은 왜 틀렸는지 알려주세요

jangcwal 4년 전 0

우선순위 큐에 경로 가중치를 제일 앞에 넣은 tuple을 넣어서 내림차순으로 정렬해줬습니다.

내리막길로 연결할 수 있는 정점들을 모두 연결하고 남은 경로의 갯수(N - cnt)의 제곱을 최소치로 잡고

오르막길로 연결할 수 있는 경로들의 갯수의 제곱에서 빼줬습니다.

연습문제도 맞고 생각한 몇개의 테케도 맞는데 어느 부분에서 틀린지를 모르겠습니다.

#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <string.h>
#include <stdio.h>
#include <tuple>
using namespace std;

const int MAX_N = 1000;
int uf[MAX_N];
typedef tuple<int, int, int> T;

int find(int n) {
	if (uf[n] < 0) return n;
	return uf[n] = find(uf[n]);
}

bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return false;
	uf[b] = a;
	return true;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int N, M;
	cin >> N >> M;
	int result_max = 0, result_min = 0;
	priority_queue<T, vector<T>, less<T>> PQ;
	fill(uf, uf + MAX_N, -1);

	for (int i = 0; i < M + 1; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		PQ.push(T(w, u, v));
	}

	int cnt = 0;
	while (cnt != N) {
		int u, v, w;
		w = get<0>(PQ.top());
		if (w == 0) {
			result_min += N - cnt;
			break;
		}
		u = get<1>(PQ.top());
		v = get<2>(PQ.top());
		PQ.pop();
		
		if (merge(u, v)) {
			cnt++;
		}
	}
	
	fill(uf, uf + MAX_N, -1);
	while (!PQ.empty()) {
		int u, v, w;
		w = get<0>(PQ.top());
		u = get<1>(PQ.top());
		v = get<2>(PQ.top());
		PQ.pop();
		
		if (w == 1) {
			continue;
		}

		if (merge(u, v)) {
			result_max += 1;
		}
	}
	cout << result_max*result_max - result_min*result_min << '\n';
	return 0;
}

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

문제

문제

출처

ICPC

13418번 반례 혹은 왜 틀렸는지 알려주세요

jangcwal 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말