From Evernote:

uva 216

先使用最小生成樹試試看，發現這不能用分岔，所以只能用暴力剪枝

[sourcecode language="cpp"]
//============================================================================
// Name : Getting in Line.cpp
// Date : 2013 2013/1/31 下午6:50:29
// Author : GCA
//============================================================================
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
#define Set(a,s) memset(a,s,sizeof(a))
#define Write(w) freopen(w,"w",stdout)
#define Read(r) freopen(r,"r",stdin)
#define Pln() printf("\n")
#define I_de(x,n)for(int i=0;i<n;i++)printf("%d ",x[i]);Pln()
#define De(x)printf(#x"%d\n",x)
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\
printf("%d ",dp[htx][hty]);}Pln();}
#define M 100005
#define PII pair<int,int>
#define PB push_back
#define oo INT_MAX
#define Set_oo 0x3f
#define Is_debug true
#define debug(...) if(Is_debug)printf("DEBUG: "),printf(__VA_ARGS__)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define eps 1e-6
bool xdy(double x,double y){return x>y+eps;}
bool xddy(double x,double y){return x>y-eps;}
bool xcy(double x,double y){return x<y-eps;}
bool xcdy(double x,double y){return x<y+eps;}
int min3(int x,int y,int z){
int tmp=min(x,y);
return min(tmp,z);
}
int max3(int x,int y,int z){
int tmp=max(x,y);
return max(tmp,z);
}
int n;
struct node_s{
int x,y;
}node[9];
double mz[9][9];
double getfar(int x1,int y1,int x2,int y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))+16;
}
double mincost=oo;
bool vis[9];
int prev[9];
vector<int> resp,tmp;
void backtrack(int i,int depth,double cost){
if(depth>=n&&cost<mincost){
resp=tmp;
mincost=cost;
return;
}
for(int j=0;j<n;j++){
if(!vis[j]&&cost<mincost){
tmp.PB(j);
vis[j]=1;
backtrack(j,depth+1,cost+mz[i][j]);
vis[j]=0;
tmp.pop_back();
}
}

}
int main() {
ios_base::sync_with_stdio(0);
int ff=0;
while(~scanf("%d",&n)&&n){
mincost=oo;
Set(vis,0);
for(int i=0;i<n;i++){
scanf("%d%d",&node[i].x,&node[i].y);
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
mz[j][i]=mz[i][j]=getfar(node[i].x,node[i].y,node[j].x,node[j].y);
}
}
for(int i=0;i<n;i++){
Set(vis,0);
backtrack(i,0,0);

}
// for(int i=0;i<resp.size();i++)
printf("**********************************************************\nNetwork #%d\n",++ff);
// printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2f feet."
// ,node[resp[i]].x,node[resp[i]].y,node[resp[i+1]].x,node[resp[i+1]].y);
printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2f feet.\n"
,node[resp[0]].x,node[resp[0]].y,node[resp[1]].x,node[resp[1]].y
,mz[resp[0]][resp[1]]);
for(uint i=1;i<resp.size()-1;i++){
printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2f feet.\n"
,node[resp[i]].x,node[resp[i]].y,node[resp[i+1]].x,node[resp[i+1]].y
,mz[resp[i]][resp[i+1]]);
}

printf("Number of feet of cable required is %.2f.\n",mincost);
}

}

[/sourcecode]