uva216 c++回溯法

因为题目要求最多8台电脑，所以可以枚举全排列，然后依次计算距离进行比较，枚举量8！=40320并不大，但这种方法不如回溯法好，当数据再大一些枚举就显得笨拙了，所以这个题我用回溯法做的，回溯有一个好处是一边生成序列一边判断，当判断这种情况下不可能满足要求时就停止向下递归，而返回上一层调用，减少运算量。

输出的时候用到了固定小数点后几位数输出的技巧，不过我还是给忘了，翻了一下以前写的博客迅速找到了，忽然切身体会到建一个自己的技术博客是多么的有意义！哈哈！

#include<iostream>#include<iomanip>#include<cstring>#include<cmath>using namespace std;struct computer{double x,y;};int n,C[8],Result[8];double Min;computer input[8];bool vis[8];double caldistance(int p1,int p2){return 16+sqrt((input[p1].x-input[p2].x)*(input[p1].x-input[p2].x)+(input[p1].y-input[p2].y)*(input[p1].y-input[p2].y));}void dfs(int cur,double sum){if (cur>1)sum=sum+caldistance(C[cur-2],C[cur-1]);if (cur==n){if (sum<Min){Min=sum;for (int i=0;i<n;i++)Result[i]=C[i];}}else if (sum>=Min) return;//已经不符合的及时返回else for (int i=0;i<n;i++){if (!vis[i]){C[cur]=i;vis[i]=1;dfs(cur+1,sum);vis[i]=0;//一定要复位！！！！勿忘！}}}int main(){int col=0;while(cin>>n&&n){col++;Min=1500;memset(vis,0,sizeof(vis));for (int i=0;i<n;i++)cin>>input[i].x>>input[i].y;dfs(0,0);cout<<"**********************************************************"<<endl;cout<<"Network #"<<col<<endl;for (int i=0;i<n-1;i++){cout<<"Cable requirement to connect ("<<fixed<<setprecision(0)<<input[Result[i]].x<<","<<input[Result[i]].y<<") to ("<<input[Result[i+1]].x<<","<<input[Result[i+1]].y<<") is "<<fixed<<setprecision(2)<<caldistance(Result[i],Result[i+1])<<" feet."<<endl;}cout<<"Number of feet of cable required is "<<fixed<<setprecision(2)<<Min<<"."<<endl;}return 0;}