글 읽기 - [1193번] 무엇이 틀렸을까요ㅠㅠ 반례 부탁드립니다.

channuu 4년 전 0

고수님들 반례나 틀린 부분 조언 주시면 감사드리겠습니다ㅠㅠ

#include <stdio.h>
#define SIZE 10001
#define Edge_SIZE 100001

struct node {
	int vertex;
	int edge;
	long long cnt;
};

node v_arr[Edge_SIZE];
node m_arr[Edge_SIZE];
int parent[SIZE];

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

bool link(int x, int y)
{
	int a = find(x);
	int b = find(y);

	if (a == b)
		return false;

	else
	{
		if (a > b)
			parent[x] = b;

		else
			parent[y] = a;
	}
	return true;
}


void mergesort(int left, int right)
{
	int li = left;
	int mid = (left + right) / 2;
	int ri = mid + 1;
	int idx = left;

	while (li <= mid && ri <= right)
	{
		if (v_arr[li].cnt > v_arr[ri].cnt)
			m_arr[idx++] = v_arr[ri++];

		else
			m_arr[idx++] = v_arr[li++];
	}

	while (li <= mid)
		m_arr[idx++] = v_arr[li++];

	while (ri <= right)
		m_arr[idx++] = v_arr[ri++];

	for (int i = left; i <= right; i++)
	{
		v_arr[i] = m_arr[i];
	}
}

void merge(int left, int right)
{
	if (right - left < 2)
	{
		if (v_arr[left].cnt > v_arr[right].cnt)
		{
			node temp = v_arr[right];
			v_arr[right] = v_arr[left];
			v_arr[left] = temp;
		}
		return;
	}

	int mid = (left + right) / 2;

	merge(left, mid);
	merge(mid + 1, right);

	mergesort(left, right);
}

int main()
{
	int V, E;
	scanf("%d %d", &V, &E);
	int start = 0;
	int end = V - 1;

	for (int i = 0; i <= SIZE; i++)
	{
		parent[i] = i;
	}

	for (int i = 0; i < E; i++)
	{
		int vertex, edge, cnt;
		scanf("%d %d %d", &vertex, &edge, &cnt);

		v_arr[i].cnt = cnt;
		v_arr[i].vertex = vertex;
		v_arr[i].edge = edge;
	}

	merge(0, E - 1);
	long long ans = 0;
	int check = 0;

	while (start <= E)
	{
		if (parent[v_arr[start].vertex] == v_arr[start].edge)
		{
			ans += v_arr[start].cnt;
			check++;
		}

		else if (link(v_arr[start].vertex, v_arr[start].edge))
		{
			ans += v_arr[start].cnt;
			check++;
		}

		if (check == end)
			break;

		start++;
	}

	printf("%lld", ans);

	return 0;
}

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

문제

문제

출처

ICPC

[1193번] 무엇이 틀렸을까요ㅠㅠ 반례 부탁드립니다.

channuu 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말