UVA216 Getting in Line

使用暴利枚舉所有可能的排列，找出最小花費時候的排列即可。

使用一個數組來保存輸入，使用一個數組來產生排列，使用另外一個數組來保存當期最小花費時候的排列。

for(int i=0;i<pointNumber;i++) 
  { 
      cin>>input[i].x>>input[i].y; 
      array[i]=i; 
      //一定要在這裡給solution賦初始值，負責solution裡面可能是空的  
      solution[i]=i; 
  } 

      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.\n", 
                    (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.\n", 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)); 
} 

#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.\n",
                    (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.\n", 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));
}