POJ 3625 Building Road（Prim）

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
#define MAXV 1005
#define INF 1e12
const int start = 1;
bool visit[MAXV] = { false };
double dist[MAXV];
int preNode[MAXV];
int vertex_size;
int road_size;
double graph[MAXV][MAXV];

struct Point{
    double x;
    double y;
};

Point pointArr[MAXV];

double calDist( Point a, Point b ){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void prim(){
    double res = 0.0;
    int nextIndex;
    int temp_node_num = vertex_size;
    for( int index = 1; index <= vertex_size; ++index ){
        dist[index] = graph[1][index];
    }
    for( int count_num = 1; count_num <= vertex_size; ++count_num ){
        double  minDistance = INF;
        int i;
        for( i = 1; i <= vertex_size; ++i ){
            if( minDistance > dist[i] && !visit[i] ){
                minDistance = dist[i];
                nextIndex = i;
            }
        }
        visit[nextIndex] = true;
      //  cout<<nextIndex<<"  "<<preNode[nextIndex]<<"    "<<graph[nextIndex][preNode[nextIndex]]<<endl;
        //if( graph[nextIndex][preNode[nextIndex]] != -1 ) res += graph[nextIndex][preNode[nextIndex]];
        for( i = 1; i <= vertex_size; ++i ){
            if( graph[nextIndex][i] < dist[i] && !visit[i] ){
                dist[i] = graph[nextIndex][i];
                //preNode[index] = nextIndex;
            }
        }
    }
    for( int i = 1; i <= vertex_size; ++i ){
        if( dist[i] != -1 ) res += dist[i];
    }
    printf( "%.2lf\n", res );
}

void init(){
    cin>>vertex_size>>road_size;
    int i, j;
    for( i = 1; i <= vertex_size; ++i ){
        cin>>pointArr[i].x>>pointArr[i].y;
    }
    for( i = 1; i <= vertex_size; ++i ){
        for( j = 1; j <= vertex_size; ++j ){
            graph[i][j] = graph[j][i] = calDist( pointArr[i], pointArr[j] );
        }
    }
    for( i = 1; i <= road_size; ++i ){
        int startPoint, endPoint;
        cin>>startPoint>>endPoint;
        graph[startPoint][endPoint] = -1;
        graph[endPoint][startPoint] = -1;
    }
}

int main(){
    init();
    prim();
    return 0;
}

POJ 3625 Building Road（Prim）

原文：http://blog.csdn.net/pandora_madara/article/details/18628809