글 읽기 - 1922 63%에서 자꾸 틀렸다고 뜹니다.

okaybody5 6년 전 0

스무스하게 크루스칼로 구현해봤는데 자꾸 오류가 뜨네요.. 어디가 잘못된거 일까요?? ㅠㅠ

고수분들 부탁드립니다 ㅠ

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge
{
    int start,end,cost;
    bool operator < (const Edge &other) const {
        return cost<other.cost;
    }
};

int p[1001];
int find(int n)
{
    if(n==p[n])
        return n;
    else
        return p[n]=find(p[n]);
}

void merge(int u,int v)
{
    u=find(u);
    v=find(v);
    p[u]=v;
} // 짜피 u!=v일때 호출되기 때문에 상관 X

int main()
{
    int N,M;
    scanf("%d %d",&N,&M);
    vector<Edge> Kruskal(100001);
    for(int i=1;i<=N;i++)
    {
        p[i]=i;
    }
    for(int i=0;i<M;i++)
    {
        scanf("%d %d %d",&Kruskal[i].start,&Kruskal[i].end,&Kruskal[i].cost);
    }
    int ans=0;
    sort(Kruskal.begin(),Kruskal.end());
    for(int i=0;i<M;i++)
    {
        Edge e=Kruskal[i];
        int x=find(e.start);
        int y=find(e.end);
        if (x!=y)
        {
            ans+=e.cost;
            merge(x,y);
        }
    }
    printf("%d",ans);
}

okaybody5 6년 전 0

해결했습니다! 33번째 줄을 숫자에서 M으로 바꾸니 AC가 떴는데, 왜 숫자로 하면 안되는지가 궁금합니다.

크루스칼을 돌 때 그것들이 0으로 초기화 되서 그런건가요?

okaybody5 6년 전 0

0ㅇ로 초기화되서 소트를 할때 0의 성분이 앞쪽으로 다 들어가서 그렇게 되는것인가요?

joonas 6년 전 1

넹. 정확해요

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

문제

문제

출처

ICPC

1922 63%에서 자꾸 틀렸다고 뜹니다.

okaybody5 6년 전 0

okaybody5 6년 전 0

okaybody5 6년 전 0

joonas 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말