글 읽기 - 전력난 문제 질문있습니다.

minjae200 5년 전 0

이 문제 간선 200,000개 입력될수 있는거 맞나요?

메모리 초과되는거같은데 다른방법없나요

문제해결을 간선의 갯수 N만큼 동적할당해서 해결하긴했는데

애초에 동적할당으로 안하고 200,000개를 MAX로 잡고 Edge[MAX]로 선언하면 아예 안돌아가서요...

다른방법이 있으면 알려주세요 ㅠㅠ

djm03178 5년 전 0

안 될 이유를 모르겠는데요. 인접 행렬이 아니라 인접 리스트를 썼다면, 메모리는 넉넉합니다.

그보다 572ms에 통과되신 코드가 어떻게 만드신 건지 궁금한데, 볼 수 있을까요?

minjae200 5년 전 0

@djm03178

흠 저도 안될이유를 모르겟는데 안되가지구 ..

코드는 여깃습니다.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX = 200000;
int M, N;
int parent[MAX];

struct Edge
{
	int u, v, w;
	Edge() :Edge(-1,-1,0) {}
	Edge(int u1,int v1,int w1) :u(u1), v(v1), w(w1) {}
	bool operator<(const Edge& e) const{ return w < e.w; }
};

int find(int num)
{
	if (parent[num] < 0) return num;
	return parent[num] = find(parent[num]);
}

bool merge(int a, int b)
{
	a = find(a); b = find(b);
	if (a == b) return false;
	if (parent[a] < parent[b]) swap(a, b);
	parent[b] += parent[a];
	parent[a] = b;
	return true;
}

int main(void)
{
	while (1)
	{
		cin >> M >> N;
		if (M == 0 && N == 0) break;
		memset(parent, -1, sizeof(parent));
		Edge *e = new Edge[N];

		int result = 0;
		for (int i = 0; i < N; i++) {
			int u, v, w;
			cin >> u >> v >> w;
			e[i] = Edge(u, v, w);
			result += e[i].w;
		}
		sort(e, e + N);
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			if (merge(e[i].u, e[i].v)) {
				result -= e[i].w;
				if (++cnt == N - 1) break;
			}
		}
		cout << result << endl;
	}
	return 0;
}