joj 1905: Freckles

http://acm.jlu.edu.cn/joj/showproblem.php?pid=1905

典型的最小生成树问题，下面C++代码实现prim算法。

#include <iostream>
#include <queue>
#include <memory.h>
#include <math.h>
using namespace std;

#define MAX ((double)(1<<30));

class Node
{
public:
    friend bool operator< (Node n1, Node n2)
    {
        return n1.key > n2.key;
    }
    int no;
    double key;
};

Node node[101];
double min_key[101];
int vis[101];
double w[101][101];

double prim(int n)
{
    memset(vis,0,sizeof(vis));
    double mst = 0.0;//最小生成树的权值
    priority_queue<Node> pri_q;
    Node node[101];
    int i,j;
    for(i=0;i<n;i++)
    {
        node[i].key = MAX;
        min_key[i] = MAX;
        node[i].no = i;
    }
    node[0].key = 0.0;//随机选择一个点，此处通过设置key值，选择0为开始节点
    min_key[0] = 0.0;
    for(i=0;i<n;i++)//开始时全部入队
    {
        pri_q.push(node[i]);
    }
    for(i=0;i<n;i++)//总共有n个节点，prim算法执行n次，找到n-1条边
    {
        Node min_node;
        while(1)//由于是重复入队，所以此处是防止最小的节点是已经访问过的节点
        {
            min_node = pri_q.top();
            pri_q.pop();
            if(!vis[min_node.no])break;
        }
        mst += min_node.key;
        vis[min_node.no] = 1;
        for(j=0;j<n;j++)//更新邻居节点
        {
            if(j!=min_node.no)
            {
                if((!vis[j])&&(w[min_node.no][j])<min_key[j])//prim算法的执行非常类似于Dijkstra算法，Dijkstra算法这里的更新策略不同
                {
                    min_key[j] = w[min_node.no][j];//配合重复入队使用，在外面保存节点的最小权值
                    Node new_node;
                    new_node.no = j;
                    new_node.key = min_key[j];
                    pri_q.push(new_node);//采用重复入队的方式，否则无法随机访问标准库优先级队列的元素
                }
            }
        }
    }
    return mst;
}

int main()
{
    int n,i,j;
    double coo_x[101],coo_y[101];
    while(cin>>n)
    {
        for(i=0;i<n;i++)
        {
            cin>>coo_x[i];
            cin>>coo_y[i];
        }
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                w[i][j] = sqrt((coo_x[i]-coo_x[j])*(coo_x[i]-coo_x[j])+(coo_y[i]-coo_y[j])*(coo_y[i]-coo_y[j]));
            }
        }
        double mst = prim(n);
        printf("%.2lf\n",mst);
    }
    return 0;
}