글 읽기 - 프림의 알고리즘을 이용했는데 안됩니다.

jja08111 3년 전 0

도무지 모르겠습니다. algospot.com의 LAN문제와 동일하게 풀었는데 안되네요...

범위 초과도 고려했는데 안됩니다.

#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
using namespace std;

const int MAX_V=1001;
const double INF=numeric_limits<double>::max( );

int V,E;
int X[MAX_V], Y[MAX_V];
double adj[MAX_V][MAX_V];

double calcDist(int u, int v)
{
    return adj[u][v]=adj[v][u]=sqrt(pow(X[u]-X[v],2)+pow(Y[u]-Y[v],2));
}

double prim()
{
    vector<int> minDist(V,INF);
    vector<bool> added(V,false);
    
    double ret=0.0;
    minDist[0]=0;
    for(int it=0;it<V;++it)
    {
        int u=-1;
        for(int v=0;v<V;++v)
            if(!added[v] && (u==-1 || minDist[u]>minDist[v]))
            {
                u=v;
                if(minDist[u]==0)
                    break;
            }
        
        added[u]=true;
        ret+=minDist[u];
        for(int v=0;v<V;++v)
        {
            if(added[v])
                continue;
            int dist=(adj[u][v]==INF) ? calcDist(u,v) : adj[u][v];
            minDist[v]=min(minDist[v],dist);
        }
    }
    return ret;
}

int main()
{
    cin>>V>>E;
    
    for(int i=0;i<V;++i)
        cin>>X[i]>>Y[i];
    
    for(int i=0;i<V;++i)
        for(int j=0;j<V;++j)
            adj[i][j]=INF;
    
    for(int i=0;i<E;++i)
    {
        int a,b;
        cin>>a>>b;
        --a; --b;
        adj[a][b]=adj[b][a]=0;
    }
    cout<<fixed;
    cout.precision(2);
    cout<<prim()<<endl;

    return 0;
}

namnamseo 3년 전 1

minDist 및 dist(43번 줄)의 타입을 확인해 주세요.

jja08111 3년 전 1

minDist가 minDistSqr였는데 이때 자료형을 int로 그대로 두어서 발생한 문제였습니다.

@namnamseo 님의 조언 감사합니다.

double prim()
{
    //vector<int> minDist(V,INF);
    vector<double> minDist(V,INF);
    vector<bool> added(V,false);
    
    double ret=0.0;
    minDist[0]=0;
    for(int it=0;it<V;++it)
    {
        int u=-1;
        for(int v=0;v<V;++v)
            if(!added[v] && (u==-1 || minDist[u]>minDist[v]))
            {
                u=v;
                if(minDist[u]==0)
                    break;
            }
        
        added[u]=true;
        ret+=minDist[u];
        for(int v=0;v<V;++v)
        {
            if(added[v])
                continue;
            //int dist=(adj[u][v]==INF) ? calcDist(u,v) : adj[u][v];
            double dist=(adj[u][v]==INF) ? calcDist(u,v) : adj[u][v];
            minDist[v]=min(minDist[v],dist);
        }
    }
    return ret;
}

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

문제

문제

출처

ICPC

프림의 알고리즘을 이용했는데 안됩니다.

jja08111 3년 전 0

namnamseo 3년 전 1

jja08111 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말