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+】