글 읽기 - 최소 스패닝 트리 시간초과...

zipbob 8년 전 0

크루스칼 알고리즘을 이용해서 구현하려고 하다가

막히는 부분이 있어서 인터넷을 찾아보니까

unite-find 자료구조가 있더라구요....

quicksort한 후에 unite-find를 통해 사이클이 안생기도록 하고

tree를 만드는 방식으로 구현했는데

시간초과가 뜨더라구요 어디서 시간초과가 발생한건가요??

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

struct edge{
    int v;
    int t;
    int c;
};

edge arr[100001];
int ran[10001];
int par[10001];

int partition(edge a[],int start,int end){
    int pivot,left,right;
    edge temp;
    left=start;
    right=end;
    pivot=(start+end)/2;
    while(left<right){
        while((a[left].c<a[pivot].c)&&(left<right))left++;
        while((a[pivot].c<a[right].c)&&(left<right))right--;
        if(left<right){
            temp=a[left];
            a[left]=a[right];
            a[right]=temp;
        }
    }
    temp=a[pivot];
    a[pivot]=a[right];
    a[right]=temp;
    return left;
}
void quickSort(edge a[], int start, int end)
{
    if(start<end)
    {
        int p ;
        p = partition(a, start, end) ;
        quickSort(a, start, p-1) ;
        quickSort(a, p+1, end) ;
    }
}
int find(int q){
    if(par[q]==q)return q;
    else return par[q]=find(par[q]);
}

void united(int q,int w){
    if(ran[q]<ran[w]){
        par[q]=w;
        ran[w]+=ran[q];
    }
    else if(ran[q]==ran[w]){
        par[q]=w;
        ran[w]+=1;
    }
    else{
        par[w]=q;
        ran[q]+=ran[w];
    }
}

int main(){
    int n,e,edgen=0;
    scanf("%d %d",&n,&e);
    for(int i=0;i<e;i++){
        scanf("%d %d %d",&arr[i].v,&arr[i].t,&arr[i].c);
    }
    quickSort(arr, 0, e-1);
    for(int i=1;i<=n;i++){
        ran[i]=0;
        par[i]=i;
    }
    int cnt=0,x,y;
    long long result=0;
    
    while(edgen!=n-1){
        x=find(arr[cnt].v);
        y=find(arr[cnt].t);
        if(x!=y){
            edgen++;
            result+=arr[cnt].c;
            united(x,y);
        }
        cnt++;
    }
    printf("%lld",result);
    
}

zipbob 8년 전 0

시간초과는 퀵정렬할때 값이 같을경우를 처리안해줘서 뜬거였네요..

퀵정렬 수정하니까 틀렸다고 나오네요..ㅠㅠ다시 찾아봐야겠습니다.

mizuharaeki 4년 전 0

left<right일때 while문을 돌리게되면 left==right가 되는 순간에 피벗과 스왑이 일어나는데, 이경우는 원래 퀵정렬의 정의와 맞지 않습니다.

퀵정렬은 left보다 right값이 작아야만, 그 부분이 피벗과 스왑이 일어납니다.

5 3 2 1 9 8 6 7

님 코드로 위 배열을 정렬하면

left가 9에서 멈추고, right역시 left<right조건때문에 left와 동일한 9에서 멈춥니다.

그럼 그게 피벗인 5와바꿔주게 되면 9 3 2 1 5 8 6 7 이잖아요.

이건 잘못된 정렬이지 않을까요?

   while(left<right){
        while((a[left].c<a[pivot].c)&&(left<right))left++;
        while((a[pivot].c<a[right].c)&&(left<right))right--;
        if(left<right){
            temp=a[left];
            a[left]=a[right];
            a[right]=temp;
        }
    }

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

문제

문제

출처

ICPC

최소 스패닝 트리 시간초과...

zipbob 8년 전 0

zipbob 8년 전 0

mizuharaeki 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말