글 읽기 - 최소 스패닝 트리 어느 부분에서 잘못됐는지 감이 안 잡힙니다 ㅠㅠ

Glitterlance 6년 전 0

결과값 범위가 틀린 것 같아서 자료형도 수정해서 했는데

한 9% 정도 올라가더니 틀렸다고 나오네요...

혹시 어느 부분이 틀렸는지 봐 주실 수 있으신가요?

#define VNUM 10001
#define ENUM 100000
#include <stdio.h>
#include <stdlib.h>

typedef struct edge {
	int v1;
	int v2;
	int cost;
}edge;

edge curEdge[ENUM];
int par[VNUM];
int rank[VNUM];

void init(int v_num) {
	for (int i = 1; i <= v_num; i++) {
		par[i] = i;
		rank[i] = 1;
	}
}

int find(int v) {
	if (par[v] == v) {
		return v;
	}
	else {
		return par[v] = find(par[v]);
	}
}

void union_find(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) {
		return;
	}

	if (rank[a] < rank[b]) {
		par[a] = b;
	}
	else {
		par[b] = a;
		if (rank[a] == rank[b]) {
			rank[a]++;
		}
	}
}

void createEdge(int e_num) {
	int v1, v2, cost;
	int curNum = 0,ins;

	for (int i = 0; i < e_num;i++) {
		scanf("%d %d %d",&v1,&v2,&cost);
		ins = ++curNum;
		while ((ins != 1) && cost < curEdge[ins/2].cost) {
			curEdge[ins] = curEdge[ins / 2];
			ins /= 2;
		}
		curEdge[ins].v1 = v1;
		curEdge[ins].v2 = v2;
		curEdge[ins].cost = cost;
	}
}

edge pop_edge(int *n) {
	int parent, child;
	edge item, temp;

	item = curEdge[1];
	temp = curEdge[(*n)--];
	parent = 1; child = 2;
	while (child <= (*n)) {
		if (child < *n && curEdge[child].cost > curEdge[child+1].cost) {
			child++;
		}
		if (temp.cost <= curEdge[child].cost) {
			break;
		}
		curEdge[parent] = curEdge[child];
		parent = child;
		child *= 2;
	}
	curEdge[parent] = temp;
	
	return item;
}

long long kruskal(int v_num,int e_num) {
	long long res = 0;
	int u_num = 0;
	int heap_num = e_num;
	edge temp;

	init(v_num);
	while (u_num < v_num - 1 && heap_num > 0) {
		temp = pop_edge(&heap_num);
		if (par[temp.v1] != par[temp.v2]) {
			union_find(temp.v1,temp.v2);
			res += temp.cost;
			u_num++;
		}
	}

	return res;
}

int main() {
	int v_num, e_num;
	long long res_cost = 0;

	scanf("%d %d", &v_num, &e_num);
	createEdge(e_num);
	printf("%lld\n",kruskal(v_num,e_num));

	return 0;
}

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

문제

문제

출처

ICPC

최소 스패닝 트리 어느 부분에서 잘못됐는지 감이 안 잡힙니다 ㅠㅠ

Glitterlance 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말