ARCTIC 문제 질문드립니다

  • dal4segno
    dal4segno
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <iostream>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    const double MAX_DISTANCE = 1.414 * 1000;
    
    typedef struct _point
    {
        double x;
        double y;
        int index;
    }point;
    
    double round( double value, int pos )
    {
        double temp;
        temp = value * pow( 10, pos );
        temp = floor( temp + 0.5 );
        temp *= pow( 10, -pos );
        return temp;
    }
    
    int main()
    {
        int C;
        scanf("%d", &C);
        while(C--)
        {
            int base_num;
            vector<point> bases;
            scanf("%d", &base_num);
            for(int i = 0 ; i < base_num ; i++)
            {
                point input;
                scanf("%lf %lf", &input.x, &input.y);
                input.index = i;
                bases.push_back(input);
            }
            double distances[100][100];
            for(int i = 0 ; i < base_num ; i++)
            {
                for(int j = 0 ; j < base_num ; j++)
                {   distances[i][j] = (i == j) ? 0 : sqrt(pow(abs(bases[j].x - bases[i].x), 2) + pow(abs(bases[j].y - bases[i].y), 2)); }
            }
            // Prim
            vector<double> my_tree;
            bool * is_checked = new bool[base_num];
            memset(is_checked, false, base_num);
            is_checked[0] = true;
            int current;
            bool OK = false;
            for(int i = 0 ; i < base_num - 1 ; i++)
            {   
                double shortest = MAX_DISTANCE;
                for(int j = 0 ; j < base_num ; j++)
                {   
                    if(is_checked[j] == true)
                    {
                        for(int k = 0 ; k < base_num ; k++)
                        {
                            if(j != k && is_checked[k] == false)
                            {   
                                if((distances[j][k] < shortest))
                                {
                                    shortest = distances[j][k]; 
                                    current = k;    
                                }
                            }
                        }
                    }
                }
                is_checked[current] = true;
                my_tree.push_back(shortest);
            }
            printf("%4.2lf\n", round(*max_element(my_tree.begin(), my_tree.end()), 3));
        }
        return 0;
    }
    

    탐사 본부를 Root 노드로 하는 MST를 구성하고, 해당 Tree에서 가장 weight?를 구하는 문제로 해석했습니다.
    MST는 프림 알고리즘을 사용했고, 반올림은 함수를 직접 제작하였습니다.
    is_checked 에 Node 사용 현황을 기록하고
    n - 1 번 동안 사용 중인 노드에서 Weight가 가장 적은 변을 선택합니다.

    예제 입력에 대한 답은 정상적으로 잘 나오는데, 오답의 예를 만들어내기 힘들어서 이렇게 질문드립니다.
    감사합니다 :)


    9년 전
1개의 댓글이 있습니다.
  • dal4segno
    dal4segno

    반올림 문제였습니다 :D


    9년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.