1344 线型网络

分析

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

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

爬山

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<cctype>
 7 
 8 using namespace std;
 9 
10 const int N = 25;
11 
12 struct Node{
13     double x,y;
14 }d[N];
15 int p[N],n;
16 double dis[N][N];
17 
18 double calcc() {
19     double ret = 0;
20     for (int i=1; i<n; ++i) 
21         ret += dis[p[i]][p[i+1]];
22     return ret;
23 }
24 double solve() {
25     double T = 1000000;
26     for (int i=1; i<=n; ++i) p[i] = i;
27     double ans = calcc();
28     while (T >= 0.001) {
29         int x = rand() % n + 1,y = rand() % n + 1;
30         swap(p[x],p[y]);
31         double tmp = calcc();
32         if (tmp < ans) ans = tmp;
33         else swap(p[x],p[y]);
34         T *= 0.96;
35     }
36     return ans;
37 }
38 int main() {
39 
40     srand(19970815);
41     scanf("%d",&n);
42     for (int i=1; i<=n; ++i) 
43         scanf("%lf%lf",&d[i].x,&d[i].y);
44     for (int i=1; i<=n; ++i) 
45         for (int j=i+1; j<=n; ++j) 
46             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));
47     solve();
48     double ans = 1e18;
49     for (int i=1; i<=20000; ++i) ans = min(ans,solve());
50     printf("%.2lf",ans);
51     return 0;
52 }

View Code

模拟退火

还没过。。