每次把元素随便扔随機一個初始解，退火時每次随機拿一個元素扔到随機一個集合裡，當溫度高時因為狀态不穩定扔到那個元素和最小的裡邊。
如果新解優，更新ans。
把原式拆一下，就可以用int存了。
bzoj 2428
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<cmath>
6 #define N 55
7 using namespace std;
8 int n,m;
9 int a[N],sum[N],be[N];
10 int ans;
11 void solve()
12 {
13 memset(sum,0,sizeof(sum));
14 int now=0;
15 for(int i=1;i<=n;i++)
16 {
17 be[i]=rand()%m+1;
18 now-=sum[be[i]]*sum[be[i]];
19 sum[be[i]]+=a[i];
20 now+=sum[be[i]]*sum[be[i]];
21 }
22 double T=10000;
23 while(T>0.1)
24 {
25 T*=0.9;
26 int x=rand()%n+1,b=be[x],y;
27 if(T>500)y=min_element(sum+1,sum+m+1)-sum;
28 else y=rand()%m+1;
29 int tmp=now;
30 now-=sum[b]*sum[b];sum[b]-=a[x];now+=sum[b]*sum[b];
31 now-=sum[y]*sum[y];sum[y]+=a[x];now+=sum[y]*sum[y];
32 if(now<tmp)be[x]=y;
33 else
34 {
35 sum[b]+=a[x];sum[y]-=a[x];
36 now=tmp;
37 }
38 }
39 ans=min(ans,now);
40 }
41 int main()
42 {
43 srand(2147483647);double sm=0;
44 ans=0x3f3f3f3f;scanf("%d%d",&n,&m);
45 for(int i=1;i<=n;i++)scanf("%d",&a[i]),sm+=a[i];
46 for(int i=1;i<=2000;i++)solve();
47 double tt=ans;tt-=sm*sm/m;tt/=m;
48 printf("%.2f\n",sqrt(tt));
49 return 0;
50 } 不懂為什麼新解沒舊解有還要有一定機率接受新解，好像不寫也能過。
bzoj 3680
求廣義費馬點，題意大概就是廣義帶權費馬點的定義吧。$$min(\sum_{i=1}^{n} dis(i,p)*hight[i])$$
參數多調幾遍就能過。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<cmath>
6 #define N 10005
7 using namespace std;
8 int n;
9 double x[N],y[N],z[N];
10 double ansx,ansy,ans;
11 double dis(double x1,double y1,double x2,double y2)
12 {
13 return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
14 }
15 inline double calc(double nx,double ny)
16 {
17 double res=0;
18 for(int i=1;i<=n;i++)
19 {
20 res+=z[i]*dis(nx,ny,x[i],y[i]);
21 }
22 return res;
23 }
24 double f()
25 {
26 int t=rand()%2;
27 if(t==0)return 1;
28 return -1;
29 }
30 double rd()
31 {
32 return rand()%10000000/10000000.0*f();
33 }
34 void solve()
35 {
36 double T=1e5;
37 while(T>=1e-5)
38 {
39 T*=0.98;
40 double xx=ansx+T*rd(),yy=ansy+T*rd();
41 double tt=calc(xx,yy);
42 if(tt<ans)
43 {
44 ans=tt;
45 ansx=xx;ansy=yy;
46 }
47 }
48 }
49 int main()
50 {
51 srand(515221650);
52 scanf("%d",&n);
53 ans=1e100;
54 for(int i=1;i<=n;i++)
55 {
56 scanf("%lf%lf%lf",&x[i],&y[i],&z[i]);
57 }
58 solve();
59 printf("%.3f %.3f\n",ansx,ansy);
60 return 0;
61 } 轉載于:https://www.cnblogs.com/ezyzy/p/6554844.html