线型网络
时间限制：1 s 内存限制：256 MB 【问题描述】
有 N(N<=20)台 PC 放在机房内，现在要求由你选定一台 PC，用共N−1条网线从这台机器开始一台接一台地依次连接他们，最后接到哪个以及连接的顺序也是由你选定的，为了节省材料，网线都拉直。求最少需要一次性购买多长的网线。(说白了,就是找出 N 的一个排列 P1P2P3..PN 然后 P1−>P2−>P3−>…−>PN 找出 |P1P2|+|P2P3|+…+|PN−1PN| 长度的最小值) 【输入格式】
第一行 N ，下面 N 行，每行分别为机器的坐标(x,y)(x为实数−100<=x,y<=100) 【输出格式】
最小的长度，保留两位小数。 【输入样例】
3 0 0 1 1 1 -1 【输出样例】
2.83
http://wenku.baidu.com/link?url=4WqYjHYHWHvhV53dZH-Iymq09wbhKNZG0nm9auH2cZaISWzeAGrrasnJSUArh8gihPQ-4ER1OkYGtIm9K9UGb-Gjw9yM6hWSgz2whs4pNo3
离散化
#include<iostream> #include<cstdio> #include<cmath> #include<stack> #include<iomanip> #include<cstdlib> #include<time.h> using namespace std; class point{ public: double x,y; }p[38]; int n; double ans=0xffffffff; double leng[38][38]={0}; int list[38]={0}; int sum=0; double dis(int a,int b){//a到b的距离 double temp=(p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y); return sqrt(temp); } void swap(int &a,int &b){ int temp; temp=a,a=b,b=temp; } void turn(int a,int b){//a<=b int i=a,j=b; while(i<=j){ swap(list[i],list[j]); i++,j--; } } void makelist(){ int i,j; for(i=1;i<=n;i++){ j=rand()%n+1; swap(list[i],list[j]); } } double count(){ double sum=0; for(int i=1;i<n;i++) sum+=leng[list[i]][list[i+1]]; return sum; } void optimize(){ int i,j; for(i=1;i<=n-1;i++){ for(j=i+1;j<=n;j++){ if(leng[list[i-1]][list[i]]+leng[list[j]][list[j+1]]>leng[list[i-1]][list[j]]+leng[list[i]][list[j+1]]){ turn(i,j); } } } } int main(){ freopen("linec.in","r",stdin); freopen("linec.out","w",stdout); scanf("%d",&n); int i,j; for(i=1;i<=n;i++) list[i]=i; for(i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); for(i=1;i<=n;i++){ for(j=1;j<i;j++) leng[j][i]=leng[i][j]=dis(i,j); } double temp; for(i=0;i<1000;i++){ makelist(); optimize(); temp=count(); if(temp<ans) ans=temp; } cout<<setiosflags(ios::fixed)<<setprecision(2)<<ans<<endl; return 0; }