216 - Getting in Line

来源:岁月联盟 编辑:猪蛋儿 时间:2012-11-13
[cpp] 
描述:水题,就不解释了…… 
 
#include <iostream> 
#include <cstdio> 
#include <cmath> 
#include <cstring> 
using namespace std; 
double count; 
int n,step[10]; 
void dfs(int cur,double sum,int *flag,int (*p)[10]) 

    if(cur>n) 
    { 
        if(sum<count) 
        { 
            count=sum; www.2cto.com
            for(int i=1; i<=n; i++) step[i]=flag[i]; 
        } 
        return; 
    } 
    else for(int i=1; i<=n; i++) 
        { 
            int j; 
            for( j=1; j<=n; j++) 
                if(flag[j]==i) break; 
            if(flag[j]==i) continue; 
            flag[cur]=i; 
            if(cur>=2) 
            { 
                int x=p[0][flag[cur-1]],y=p[1][flag[cur-1]]; 
                double c=sqrt((p[0][i]-x)*(p[0][i]-x)+(p[1][i]-y)*(p[1][i]-y)); 
                dfs(cur+1,sum+c,flag,p); 
            } 
            else dfs(cur+1,sum,flag,p); 
            flag[cur]=0; 
        } 

int main() 

#ifndef ONLINE_JUDGE 
    freopen("a.txt","r",stdin); 
#endif 
    int j(0),num[2][10],flag[10]; 
    while(scanf("%d",&n)!=EOF) 
    { 
        if(!n) break; 
        memset(num,0,sizeof(num)); 
        memset(flag,0,sizeof(flag)); 
        printf("**********************************************************/n"); 
        printf("Network #%d/n",++j); 
        count=100000; 
        for(int i=1; i<=n; i++) 
            scanf("%d%d",&num[0][i],&num[1][i]); 
        dfs(1,0,flag,num); 
        for(int i=1; i<n; i++) 
        { 
            int x1=num[0][step[i]],y1=num[1][step[i]],x2=num[0][step[i+1]],y2=num[1][step[i+1]]; 
            printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2lf feet./n",x1,y1,x2,y2,sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))+16); 
        } 
        printf("Number of feet of cable required is %.2lf./n",count+(n-1)*16); 
    } 
    return 0;