每次把元素随便扔随机一个初始解，退火时每次随机拿一个元素扔到随机一个集合里，当温度高时因为状态不稳定扔到那个元素和最小的里边。
如果新解优，更新ans。
把原式拆一下，就可以用int存了。
bzoj 2428
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 55
using namespace std;
int n,m;
int a[N],sum[N],be[N];
int ans;
void solve()
{
memset(sum,,sizeof(sum));
int now=;
for(int i=;i<=n;i++)
{
be[i]=rand()%m+;
now-=sum[be[i]]*sum[be[i]];
sum[be[i]]+=a[i];
now+=sum[be[i]]*sum[be[i]];
}
double T=;
while(T>0.1)
{
T*=0.9;
int x=rand()%n+,b=be[x],y;
if(T>)y=min_element(sum+,sum+m+)-sum;
else y=rand()%m+;
int tmp=now;
now-=sum[b]*sum[b];sum[b]-=a[x];now+=sum[b]*sum[b];
now-=sum[y]*sum[y];sum[y]+=a[x];now+=sum[y]*sum[y];
if(now<tmp)be[x]=y;
else
{
sum[b]+=a[x];sum[y]-=a[x];
now=tmp;
}
}
ans=min(ans,now);
}
int main()
{
srand();double sm=;
ans=0x3f3f3f3f;scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%d",&a[i]),sm+=a[i];
for(int i=;i<=;i++)solve();
double tt=ans;tt-=sm*sm/m;tt/=m;
printf("%.2f\n",sqrt(tt));
return ;
}
不懂为什么新解没旧解有还要有一定概率接受新解，好像不写也能过。
bzoj 3680
求广义费马点，题意大概就是广义带权费马点的定义吧。$$min(\sum_{i=1}^{n} dis(i,p)*hight[i])$$
参数多调几遍就能过。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 10005
using namespace std;
int n;
double x[N],y[N],z[N];
double ansx,ansy,ans;
double dis(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
inline double calc(double nx,double ny)
{
double res=;
for(int i=;i<=n;i++)
{
res+=z[i]*dis(nx,ny,x[i],y[i]);
}
return res;
}
double f()
{
int t=rand()%;
if(t==)return ;
return -;
}
double rd()
{
return rand()%/10000000.0*f();
}
void solve()
{
double T=1e5;
while(T>=1e-)
{
T*=0.98;
double xx=ansx+T*rd(),yy=ansy+T*rd();
double tt=calc(xx,yy);
if(tt<ans)
{
ans=tt;
ansx=xx;ansy=yy;
}
}
}
int main()
{
srand();
scanf("%d",&n);
ans=1e100;
for(int i=;i<=n;i++)
{
scanf("%lf%lf%lf",&x[i],&y[i],&z[i]);
}
solve();
printf("%.3f %.3f\n",ansx,ansy);
return ;
}