UVA10228 A Star not a Tree?

题目

题目

思路

可以使用模拟退火解决。
模拟退火是一个基于物理随机化的算法，有一个类比：
随着时间流逝，高温液体慢慢冷却下来，原子交换顺序慢慢变得缓慢。
我们模仿原子的交换（随机化处理）以更新答案。
若当前答案不如新答案优，则更新，同时以后的退火都以现答案为标准。
否则，一定概率让以后的退火都以现答案为标准，不更新答案。
代码实现：

		if (del<0) ans=u,ssx=sx,ssy=sy,sx=wj2,sy=lyw2;else if (exp(-del/time)*RAND_MAX>rand()) sx=wj2,sy=lyw2;

这里的原子交换是模拟伪·费马点的移动，公式：

		wj2=sx+((rand()<<1)-RAND_MAX)*time,lyw2=sy+((rand()<<1)-RAND_MAX)*time;

代码截取，了解即可，RAND_MAX=32767
计算伪·答案可暴力。
显然该算法可能WA，但我们可以多做几次，好比我们把液体加热，凝固，加热，再凝固……（就是饭堂的食品啦）
记得，一定要注意精度
还有输出格式，详见代码
code:

#include
#include
#include
#include
#include
#include
using namespace std;
long long n,t;
double b[1220][2],delta=0.994,r,sx,sy,ssx,ssy,ans;
inline long long read()
{long long s=0;int z=1;char c=getchar();if (c=='-') z=-1;while ((c<'0'||c>'9')&&c!='-') c=getchar();if (c=='-') z=-1,c=getchar();while (c>='0'&&c<='9') s=(s<<1)+(s<<3)+(c^48),c=getchar();return z*s;
}
inline double Fread()
{char c=getchar();int flag=1;double s=0;while ((!(c>='0'&&c<='9'))&&c!='-') c=getchar();if (c=='-') flag=-1,c=getchar();while (c>='0'&&c<='9') s=s*10+(c^48),c=getchar();if (c=='.'){c=getchar();for (int x=10;c>='0'&&c<='9';x=(x<<3)+(x<<1)) s+=(double)(c^48)*1.0/x,c=getchar();}return s*flag;
}
double jl(double x,double y,double x2,double y2)
{return sqrt((x-x2)*(x-x2)+(y-y2)*(y-y2));
}
double kyx(double wj2,double lyw2)
{double rr=0;for (int i=1;i<=n;i++){rr+=jl(wj2,lyw2,b[i][0],b[i][1]);}return rr;
}
void SA()//模拟退火，别名SA
{sx=ssx,sy=ssy;double wj2,lyw2;for (double time=2333;time>1e-10;time*=delta){wj2=sx+((rand()<<1)-RAND_MAX)*time,lyw2=sy+((rand()<<1)-RAND_MAX)*time;double u=kyx(wj2,lyw2),del=u-ans;if (del<0) ans=u,ssx=sx,ssy=sy,sx=wj2,sy=lyw2;else if (exp(-del/time)*RAND_MAX>rand()) sx=wj2,sy=lyw2;}return;
}
int main()
{t=read();while (t--){n=read();sx=sy=0;for (int i=1;i<=n;i++) b[i][0]=Fread(),b[i][1]=Fread(),sx+=b[i][0],sy+=b[i][1];sx/=n,sy/=n;ssx=sx,ssy=sy;ans=kyx(sx,sy);SA(),SA(),SA();printf("%.0lf\n",ans);if (t) printf("\n");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！