BZOJ 3680: 吊打XXX【模拟退火算法裸题学习，爬山算法学习】

Time Limit: 10 Sec  Memory Limit: 128 MBSec  Special Judge

Submit: 3192  Solved: 1198

gty又虐了一场比赛，被虐的蒟蒻们决定吊打gty。gty见大势不好机智的分出了n个分身，但还是被人多势众的蒟蒻抓住了。蒟蒻们将

n个gty吊在n根绳子上，每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。吊好gty后蒟蒻们发现由于每个gty重力不同，绳

结x在移动。蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标，由于他太弱了决定向你求助。

不计摩擦，不计能量损失，由于gty足够矮所以不会掉到地上。

输入第一行为一个正整数n(1<=n<=10000)，表示gty的数目。

接下来n行,每行三个整数xi，yi，wi，表示第i个gty的横坐标，纵坐标和重力。

对于20%的数据，gty排列成一条直线。

对于50%的数据，1<=n<=1000。

对于100%的数据，1<=n<=10000,-100000<=xi,yi<=100000

输出1行两个浮点数（保留到小数点后3位），表示最终x的横、纵坐标。

3

0 0 1

0 2 1

1 1 1

0.577 1.000

<a href="http://www.lydsy.com/JudgeOnline/problemset.php?search=By%20wangxz">By wangxz</a>

分析：我反正是被坑死啦，这题谁跟我说是水题的，！！！！！模拟退火算法-----高级，爬山算法------今天才听说过QAQ，好的吧，学习一下，毕竟是道裸题~~~

题目大意：给定n个质点，求重心，这n个质点的重心满足Σ(重心到点i的距离)*g[i]最小，模拟退火的裸题，这题INF开0x3f妥妥过不去。。。起码要max_of _long_long附近才可以！

思路：puts("nan nan");得AC//BZOJ貌似是这个样子的呢，很多题这样写都会AC

爬山就够了，模拟退火也可以。

模拟退火就是在模拟一个退火的过程，他和爬山的区别就在于，它多了一个温度参数。

我们可以发现，越到后面，我们就越接近。所以我们应该把修改的范围越改越小，接受较劣解的可能性也应该调小。

于是我们引入一个温度变量T，膜你退火的过程，温度逐渐下降。

下面给出模拟退火的流程：

设定初始较高的温度T

      while 温度&gt;设定的最低值

         随机得到一个新解（温度越高，新解与旧解的差异越大）

         更新答案

         根据新解与旧解之间的优劣关系，以一定概率接受新解（越优越有可能）

         以一定方式降温

      endwhile

为了保证答案的质量，我们可以在最优解附近再进行随机，并更新答案

模拟退火代码如下：【代码跑的很慢很慢。10000ms+】

爬山算法代码如下【快了8000ms+】