ACM UVA 10034 (Problem A: Freckles)

题目：

 

思路： 最小生成树

 

代码：

 

/*
 * =============================================================================
 *
 * Filename: 10034.cpp
 *
 * Description: Use Prim's algorithm
 *
 * Version: 0.1
 * Created: 6/3/2009 8:37:15 PM
 *
 * Author: Ye Xiaofeng, yexfeng # gmail.com
 *
 * =============================================================================
 */

#include <iostream>
#include <iomanip>
#include <list>
#include <cmath>

using namespace std;

struct Freckle {
    float x;
    float y;
};

float lenFreckle(Freckle& f1, Freckle& f2)
{
    return sqrt((f1.x-f2.x)*(f1.x-f2.x)+(f1.y-f2.y)*(f1.y-f2.y));
}

int main()
{
    int caseNum = 0;
    
    cin >> caseNum;
    for (; caseNum != 0; caseNum--) {
        int freckleNum;
        list<Freckle> candiList;
        list<Freckle> usedList;
        Freckle freckle;
        cin >> freckleNum;
        for (int i = 0; i < freckleNum; i++) {
            cin >> freckle.x >> freckle.y;
            candiList.push_back(freckle);
        }
        float result = 0;
        freckle = candiList.front();
        usedList.push_back(freckle);
        candiList.pop_front();
        for (int usedCount = 1; usedCount < freckleNum; usedCount++) {
            float minVal = 0;
            list<Freckle>::iterator candiIter = candiList.begin();
            list<Freckle>::iterator minIter;
            for (; candiIter != candiList.end(); candiIter++) {
                Freckle candiFreckle = *candiIter;
                list<Freckle>::iterator usedIter = usedList.begin();
                for (; usedIter != usedList.end(); usedIter++) {
                    Freckle usedFreckle = *usedIter;
                    float curLen = lenFreckle(candiFreckle, usedFreckle);
                    if (0 == minVal) {
                        minVal = curLen;
                            minIter = candiIter;
                    } else {
                        if (minVal > curLen) {
                            minVal = curLen;
                            minIter = candiIter;
                        }
                    }
                }
            }
            usedList.push_back(*minIter);
            candiList.erase(minIter);
            result += minVal;
        }
        cout << fixed << setprecision(2) << result << endl;
        if (caseNum != 1) {
            cout << endl;
        }
    }
}