216 Getting in Line: 这个题是做了差不多一天的。其中犯了不少错，主要是一些细节：比如 = 写成 == 。\n 另外，这里要用到排列生成，而不是用子集。这是我范的比较严重的错误，导致算法就错了。\n 另外，坐标是整数，而不是实数，我直接想当然给弄成了double了，导致一直WA，这就是不认真的后果。\n 做这个题最大的收获：1，信心越来越强了，之前没做过ACM的题，看到这么长的题，都不敢想象自己能做出来。从开始刷题到现在，已经完成了5个题，信心越来越强；2，端正了自己的态度，正确看待刷题这件事，我是一个很不喜欢做题的人，而且之前对ACM题有个误解，以为应该像写快排程序那样，时间不超过5分钟，代码不超过30行，哈哈，我之前真是又傻又天真。现在我知道了，刷题和我之前看论文…

gistfile1.cpp

正确代码：
#include <iostream>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#define N 10

using namespace std;

double dismatrix[N][N];
int line[N];
double INF=999999999999.0;
double maxm;
int order[N];
struct coor{
    int x;
    int y;
};

double dist(int a,int b, int c,int d){
    double k = sqrt((a-c)*(a-c)+(b-d)*(b-d))+16.0;
    return k;
}

void searchline(int *line, double len,int n,int cur){
    if(cur == n){//当产生一个排列之后
        //len = 0.0;
        for(int i = 1; i < n; i++){
            len += dismatrix[line[i-1] - 1][line[i] - 1];//计算一下该排列需要的线的总长度。
            if(len > maxm) return;//如果一不小心，还没统计完就发现大于了已知最小的，直接返回。
        }
        if(len < maxm) {//统计结束后发现小于已知最小的。
             for(int i = 0; i < n; i++)
                order[i] = line[i] - 1;//则复制该排列。
                maxm = len;//更新最小长度。
        }
        return;
    }
    else for(int i = 1; i <= n; i++){//注意要从1开始，因为line的初始化就是0，
            //所以如果从0开始对比的话，第一个0肯定存在，导致出错。
        int ok = 1;
        for(int j = 0; j < cur; j++)
            if(line[j] == i) ok = 0;
        if(ok){
            line[cur] = i;
            searchline(line,len,n,cur+1);
        }
    }//整个过程就是产生一个1-n的排列。
}

int main(){
    int n;
    int num = 0;
    while(cin>>n){
        if(n == 0) break;//读到末尾就停止。
        maxm = INF;
        struct coor coordinate[N];//存放坐标的结构体
        memset(coordinate,0,sizeof(coor)*n);

        memset(dismatrix,0,sizeof(dismatrix));//存放各个距离的二维数组
        for(int i = 0; i < n; i++){//读入各个点的坐标
            cin>>coordinate[i].x>>coordinate[i].y;
        }
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){//计算距离矩阵
                double d = dist(coordinate[i].x,coordinate[i].y, \
                                       coordinate[j].x,coordinate[j].y);
                dismatrix[i][j] = dismatrix[j][i] = d;
            }
        }
        int cur = 0;
        double len = 0.0;
        memset(line,0,sizeof(line));
        memset(order,0,sizeof(order));
        cout<<"**********************************************************\n";
        cout << "Network #" << ++num << endl;
        searchline(line,len,n,cur);
        for(int i = 1; i < n; i++){
            cout<<"Cable requirement to connect (";
            cout<<coordinate[order[i-1]].x<<","<<coordinate[order[i-1]].y;
            cout<<") to (";
            cout<<coordinate[order[i]].x<<","<<coordinate[order[i]].y;
            cout<<") is ";
            cout.setf(ios::fixed);
            cout.precision(2);
            cout<<dismatrix[order[i-1]][order[i]];
            cout<<" feet."<<endl;
            cout.precision(0);
        }
        cout.precision(2);
        cout<<"Number of feet of cable required is ";
        cout<<maxm<<"."<<endl;
        cout.precision(0);
    }
    return 0;
}
//------------------------------------------------------------
最后再来个之前以为要用子集的代码，也就是错误代码：
#include <iostream>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstdlib>
#define N 10
using namespace std;

double dismatrix[N][N];
int visit[N][N];
int line[N];
double maxm;

struct coor{
    double x;
    double y;
};
double dist(double a,double b, double c,double d){
    double k = sqrt((a-c)*(a-c)+(b-d)*(b-d))+16;
    return k;
}

void searchline(double &maxm, double len,int n,int cur){
    /*for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cout<<visit[i][j]<<" ";
        }
        cout<<endl;
    }*/

    if(cur == n-1){
        if(len < maxm)
            maxm = len;
        len = 0.0;
        return;
    }
    else for(int i = 0; i < n; i++)if(!visit[cur][i] && i != cur){
            //if(cur == 0) len = 0;
        len += dismatrix[cur][i];
        //cout<<cur<<" "<<i<<" "<<len<<endl;
        //visit[cur][i] == 1;
        visit[i][cur] = 1;
        line[cur] = i;

        searchline(maxm,len,n,cur+1);

        //visit[cur][i] == 0;
        visit[i][cur] = 0;

        len -= dismatrix[cur][i];
        //line[cur] = -1;
    }
}

int main(){
    ifstream fin;
    fin.open("D:\\C++\\test\\bin\\Debug\\123");
    int n;
    while(fin>>n){
        if(n == 0) break;
        struct coor coordinate[N];
        memset(coordinate,0,sizeof(coor)*N);

        memset(dismatrix,0,sizeof(dismatrix));
        for(int i = 0; i < n; i++){
            fin>>coordinate[i].x>>coordinate[i].y;
        }
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                double d = dist(coordinate[i].x,coordinate[i].y, \
                                       coordinate[j].x,coordinate[j].y);
                dismatrix[i][j] = dismatrix[j][i] = d;
            }
            //sort(dismatrix[i], dismatrix[i]+n);
        }
        int cur = 0;
        maxm = 9999.0;
        double len = 0.0;
        int time = 0;
        memset(line, 0 ,sizeof(line));
        memset(visit,0,sizeof(visit));
        for(int i = 0; i < n; i++) line[i] = -1;
        //for(int i = 0; i < n; i++){
            //cur = i;
            searchline(maxm,len,n,cur);
        //}
        cout<<"maxm = "<<maxm<<endl;

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                cout<<dismatrix[i][j]<<" ";
            }
            cout<<endl;
        }

        for(int i = 0; i < n; i++)
            cout<<line[i]<<" ";
        cout<<endl;
    }
    return 0;
}