[cogs6]线性网络

发表于 2017-08-11   |   分类于 未分类  |  访问: 24 次

题目

【问题描述】
有 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)

【输出格式】
最小的长度,保留两位小数。

做法是随机化贪心
先随机的打乱点,然后暴力的判断两点交换以后花费是否较小,是的话就交换
有趣的是随机的正确概率很小,贪心的正确概率也是非常小的
但两者合在一起,正确率却几乎是100%

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cmath>
using namespace std;
struct e{
    double x,y;
}a[30];
int n,b[30];
double g[30][30];
double min(double x,double y){
    if(x>y)        return y;
    return x;
}
double work(){
    double sum=0;
    for(int i=2;i<=n;i++)
        sum+=g[b[i-1]][b[i]];
    return sum;
}
void sv(int x,int y){
    int i,j;
    for(i=x,j=y;i<=j;i++,j--)
        swap(b[i],b[j]);
}
void change(){
    for(int i=1;i<=15;i++)
        swap(b[rand()%n+1],b[rand()%n+1]);
    for(int i=1;i<=n-1;i++)
        for(int j=i+1;j<=n;j++)
            if(g[b[i-1]][b[i]]+g[b[j]][b[j+1]] > g[b[i-1]][b[j]]+g[b[i]][b[j+1]])
                sv(i,j);
}
int main(){
    freopen("linec.in","r",stdin);
    freopen("linec.out","w",stdout);
    double ans=2100000000;
    srand(time(NULL));
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lf%lf",&a[i].x,&a[i].y);
        for(int j=1;j<i;j++)
            g[i][j]=g[j][i]=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
        b[i]=i;
    }
    for(int i=1;i<800;i++){
        change();
        ans=min(ans,work());
    }
    printf("%.2lf\n",ans);
    return 0;
}

发表新评论

© 2017 Powered by Typecho & Theme Quark