글 읽기 - cpp 우선순위 큐를 이용한 크루스칼 알고리즘 질문입니다.

kibum1024 2년 전 0

몇 개 예시 넣어서 돌려봐도 잘 나오고 그러는데 왜 틀렸다고 나오는지 모르겠습니다ㅠㅠ

고수님들 도와주시면 정말 감사합니다!!

#include<cstdio>
#include<vector>
#include<utility>
#include<queue>
#include<cmath>
using namespace std;
pair<int,int> par[1111];
pair<double,double> point[1111];

struct edge{
  double w;
  int s,e;
};

struct cmp{
  bool operator()(edge A,edge B){
    return A.w>B.w;
  }
};

double dist(int i,int j){
  return sqrt((point[i].first-point[j].first)*(point[i].first-point[j].first)+(point[i].second-point[j].second)*(point[i].second-point[j].second));
}

int parent(int x){
  if(par[x].first==x) return x;
  return par[x].first = parent(par[x].first);
}


int main(){
  int n,m,i,j,k;
  int ps,pe;
  double x,y,ans=0;
  scanf("%d %d",&n,&m);
  for(i=0;i<=n;i++) par[i] = {i,0};
  for(i=1;i<=n;i++){
    scanf("%lf %lf",&x,&y);
    point[i] = {x,y};
  }

  //가능한 모든 간선을 우선순위 큐에 대입
  priority_queue<edge,vector<edge>,cmp> pq;
  for(i=1;i<=n;i++){
    for(j=i+1;j<=n;j++){
      pq.push({dist(i,j),i,j});
    }
  }
  for(i=0;i<m;i++){
    scanf("%d %d",&j,&k);
    pq.push({0,j,k});
  }

  //거리가 가장 짧은 것만 뽑으면서 union 알고리즘 적용
  while(!pq.empty()){
    edge temp = pq.top();
    //printf("%lf %d %d\n",temp.w,temp.s,temp.e);
    pq.pop();
    ps = parent(temp.s), pe = parent(temp.e);
    if(ps==pe) continue;
    //트리 높이가 작은 거를 큰 쪽으로 합치는 과정
    else if(par[ps].second>par[pe].second) par[pe].first = ps;
    else if(par[pe].second>par[ps].second) par[ps].first = pe;
    else par[pe].first = ps, par[ps].second++;
    ans+=temp.w;
  }
  printf("%.2f",ans+0.005); // 소수점 아래 3번째에서 반올림
}

Green55 2년 전 0

지문이 좀 이상하게 쓰여있는데 그냥 printf("%.2f",ans) 하시면 됩니다

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

문제

문제

출처

ICPC

cpp 우선순위 큐를 이용한 크루스칼 알고리즘 질문입니다.

kibum1024 2년 전 0

Green55 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말