글 읽기 - 최소 스패닝 트리 질문입니다.

zipbob 8년 전 0

크루스칼 알고리즘으로 짯는데

메모리 초과떳네요

다른 알고리즘으로 해결해야하나요??

#include<iostream>
#include<vector>
#include<cstdio>
#include<queue>
#include<math.h>

using namespace std;
#define min(a,b) a<b?a:b
int arr[100001][3];
int par[100001];
int ran[100001];
priority_queue<pair<int,pair<int,int> > > q;
int n;

int find(int q){
    if(par[q]==q)return q;
    else return par[q]=find(par[q]);
}
void united(int p,int q){
    if(ran[p]>ran[q]){
        par[q]=p;
    }
    else{
        par[p]=q;
        if(ran[p]==ran[q])
            ran[q]++;
    }
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        par[i]=i;
        ran[i]=0;
        scanf("%d %d %d",&arr[i][0],&arr[i][1],&arr[i][2]);
    }
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            int cost=min(abs(arr[i][0]-arr[j][0]),min(abs(arr[i][1]-arr[j][1]),abs(arr[i][2]-arr[j][2])));
            q.push(make_pair(-cost,make_pair(i,j)));
        }
    }
    
    
    int edgenum=0;
    int ans=0;
    while(edgenum+1!=n){
        int x=find(q.top().second.first);
        int y=find(q.top().second.second);
        int cost=-q.top().first;
        q.pop();
        if(x!=y){
            edgenum++;
            ans+=cost;
            united(x,y);
        }
    }
    printf("%d",ans);
}

nisroeld99 7년 전 0

크루스칼은 맞는데

입력시 행성간의 모든 간선을 추가해버리면 TLE 가 나오고 인접한 짧은 거리만 추가해주면됩니다.

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

문제

문제

출처

ICPC

최소 스패닝 트리 질문입니다.

zipbob 8년 전 0

nisroeld99 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말