来自 Evernote:#
uva 216#
先使用最小生成树试试看，发现这不能用分岔，所以只能用暴力剪枝
[sourcecode language="cpp"]
//============================================================================
// 名称 : Getting in Line.cpp
// 日期 : 2013 2013/1/31 下午 6:50:29
// 作者 : GCA
//============================================================================
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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 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 ("**********************************************************\n 网络 #% d\n",++ff);
//printf ("连接 (% d,% d) 到 (% d,% d) 的电缆需求是 %.2f 英尺。"
// ,node[resp[i]].x,node[resp[i]].y,node[resp[i+1]].x,node[resp[i+1]].y);
printf ("连接 (% d,% d) 到 (% d,% d) 的电缆需求是 %.2f 英尺。\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 ("连接 (% d,% d) 到 (% d,% d) 的电缆需求是 %.2f 英尺。\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 ("所需电缆的总英尺数是 %.2f。\n",mincost);
}
}
[/sourcecode]