UVA216 Getting in Line

题目链接：UVA216

使用暴利枚举所有可能的排列，找出最小花费时候的排列即可。

使用一个数组来保存输入，使用一个数组来产生排列，使用另外一个数组来保存当期最小花费时候的排列。

      for(int i=0;i<pointNumber;i++)
        {
            cin>>input[i].x>>input[i].y;
            array[i]=i;
            //一定要在这里给solution赋初始值，负责solution里面可能是空的
            solution[i]=i;
        }

一定要在初始的时候就给保存结果的数组赋初始值，因为第一个排列可能就是最优解。如果第一个就是最优解的话那么..........我就是因为没有给它赋值，而Wrong Answer的好多次.

具体看代码：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
struct point
{
    int x;
    int y;
}input[10];     //记录坐标
double getDistance(double,double,double,double);
int main()
{
    int pointNumber;
    int count=1;
    while(cin>>pointNumber,pointNumber!=0)
    {
        int solution[8];     //存储每次更新后的顺序
        int array[8];
        for(int i=0;i<pointNumber;i++)
        {
            cin>>input[i].x>>input[i].y;
            array[i]=i;
            //一定要在这里给solution赋初始值，负责solution里面可能是空的
            solution[i]=i;
        }

        double minCost;
        double tempNumber=0;
        for(int i=0;i<pointNumber-1;i++)
            tempNumber+=getDistance(input[array[i]].x,input[array[i]].y,input[array[i+1]].x,input[array[i+1]].y);
        minCost=tempNumber;
        while(next_permutation(array,array+pointNumber))
        {
            //计算对应全排列时的花费
            tempNumber=0;
            for(int i=0;i<pointNumber-1;i++)
            {
                tempNumber+=getDistance(input[array[i]].x,input[array[i]].y,input[array[i+1]].x,input[array[i+1]].y);
            }
            if(tempNumber<minCost)
            {
                minCost=tempNumber;
                memcpy(solution,array,sizeof(array));
            }
        }
        cout<<"**********************************************************"<<endl;
        cout<<"Network #"<<count++<<endl;
        for(int i=0;i<pointNumber-1;i++)
        {
            double cost=getDistance(input[solution[i]].x,input[solution[i]].y,input[solution[i+1]].x,input[solution[i+1]].y);
            printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2lf feet.
",
                    (int)input[solution[i]].x,(int)input[solution[i]].y,(int)input[solution[i+1]].x,(int)input[solution[i+1]].y, cost+16);
        }
        printf("Number of feet of cable required is %.2lf.
", minCost+16*(pointNumber-1));
    }
    return 0;
}
double getDistance(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}