1344 线型网络

1344 线型网络

链接

 

分析

　　先写了个爬山，一直不过，然后调整变量的初始范围，不断调整，终于终于终于A了9个点，然后在调了一下，最后过了。。。爬山求的要次数尽量多一些。

　　然后又写了模拟退火，调整了初始范围。模拟退火，求的次数可以不用太多，它会有一定的几率跳到不优的点。

 

爬山

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>

using namespace std;

const int N = 25;

struct Node{
    double x,y;
}d[N];
int p[N],n;
double dis[N][N];

double calcc() {
    double ret = 0;
    for (int i=1; i<n; ++i) 
        ret += dis[p[i]][p[i+1]];
    return ret;
}
double solve() {
    double T = 1000000;
    for (int i=1; i<=n; ++i) p[i] = i;
    double ans = calcc();
    while (T >= 0.001) {
        int x = rand() % n + 1,y = rand() % n + 1;
        swap(p[x],p[y]);
        double tmp = calcc();
        if (tmp < ans) ans = tmp;
        else swap(p[x],p[y]);
        T *= 0.96;
    }
    return ans;
}
int main() {

    srand(19970815);
    scanf("%d",&n);
    for (int i=1; i<=n; ++i) 
        scanf("%lf%lf",&d[i].x,&d[i].y);
    for (int i=1; i<=n; ++i) 
        for (int j=i+1; j<=n; ++j) 
            dis[i][j] = dis[j][i] = sqrt((d[i].x-d[j].x)*(d[i].x-d[j].x)+(d[i].y-d[j].y)*(d[i].y-d[j].y));
    solve();
    double ans = 1e18;
    for (int i=1; i<=20000; ++i) ans = min(ans,solve());
    printf("%.2lf",ans);
    return 0;
}

 

模拟退火

还没过。。