글 읽기 - 최소 스패닝 트리 문제가 잘 안됩니다.

yeop9657 8년 전 0

안녕하세요.

자꾸 틀렸다고 하는데 어디에 문제가 있는 건가요?

#include <iostream>
#include <algorithm>
#define SIZE 100010
using namespace std;

/* Struct */
typedef struct edge * ePtr;
typedef struct edge
{
	int N; /* 시작점 */
	int M; /* 도착점 */
	int W; /* 가중치 */
} Edge;

/* Edge */
Edge mEdge[SIZE];

/* Integer */
int MAX[SIZE];

/* Kruskal Algorithm */
int Kruskal(int N, int M)
{
	/* Integer */
	int mSum = 0; /* 가중치의 합을 저장하는 변수 */

	/* 정점의 수 만큼 배열 초기화 */
	for (int ii = 1; ii <= N; ii++) { MAX[ii] = ii; }
	for (int jj = 0; jj < M; jj++)
	{
		if (MAX[mEdge[jj].N] != MAX[mEdge[jj].M])
		{
			MAX[mEdge[jj].N] < MAX[mEdge[jj].M] ? MAX[mEdge[jj].M] = MAX[mEdge[jj].N] : MAX[mEdge[jj].N] = MAX[mEdge[jj].M];

			/* 가중차 합 저장 */
			mSum += mEdge[jj].W;
		}
	}

	return mSum;
}

/* Compare */
int Compare(const void * v1, const void * v2)
{ return ((ePtr)v1)->W > ((ePtr)v2)->W ? 1 : 0; }

int main(void)
{
	/* Integer */
	int num1 = 0, num2 = 0;
	cin >> num1 >> num2;

	/* Input */
	for (int count = 0; count < num2; count++)
	{
		cin >> mEdge[count].N >> mEdge[count].M >> mEdge[count].W;
	}

	/* Qsort */
	qsort((void *)mEdge, num2, sizeof(mEdge[0]), Compare);

	/* output */
	cout << Kruskal(num1, num2) << endl;

	return 0;
}

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

문제

문제

출처

ICPC

최소 스패닝 트리 문제가 잘 안됩니다.

yeop9657 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말