正解又不會寫，又懶得去想
只好每次考試大大暴力，維持一下生活了
-----------------------
P1337 [JSOI2004]平衡點 / 吊打XXX
題目描述
有n個重物，每個重物系在一條足夠長的繩子上。每條繩子自上而下穿過桌面上的洞，然后系在一起。圖中X處就是公共的繩結。假設繩子是完全彈性的（不會造成能量損失），桌子足夠高（因而重物不會垂到地上），且忽略所有的摩擦。
問繩結X最終平衡于何處。
注意：桌面上的洞都比繩結X小得多，所以即使某個重物特別重，繩結X也不可能穿過桌面上的洞掉下來，最多是卡在某個洞口處。
這道題，是一道模你模擬退火的板子題
我是看這個大佬看懂的
我一開始看這個算法，是拒絕的。你不能叫我玄學就玄學。
然鵝這是玄學的特技，是特技的玄學。對于搜索偏分還是很好用的
提醒：公式不要死磕
exp是計算自然對數次方的函數
參數是個玄學的東西，要不斷地摸索和聯系
解不一定是最優，但時間復雜度低
算法大概：
從當前狀態通過一個不斷縮減的步長轉移到下一個狀態
然后計算待轉移狀態的優劣程度，這個優劣程度就是能量
然后比當前狀態優的話，就貪心的進行轉移
不優的話，就根據那個鬼的公式。算概率轉移
假ac代碼：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<cmath>
const int maxn=10100;
const double eps=1e-14;
struct node
{int x,y;int w;
};
node pos[maxn];
int n;
double anx,any;
double calc(double x,double y)
{double res=0;for(int i=1;i<=n;i++){double px=x-pos[i].x;double py=y-pos[i].y;res+=sqrt(px*px+py*py)*pos[i].w;}return res;
}
void simulate()
{double t=250;while(t>eps){double nowx=anx+((rand()<<1)-RAND_MAX)*t;double nowy=any+((rand()<<1)-RAND_MAX)*t;double delta_E=calc(nowx,nowy)-calc(anx,any);if(delta_E<0)anx=nowx,any=nowy;else if(exp(-delta_E/t)*RAND_MAX>rand())anx=nowx,any=nowy;t=t*0.997;}
}
int main()
{srand(臉);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d%d",&pos[i].x,&pos[i].y,&pos[i].w);anx+=pos[i].x;any+=pos[i].y;}anx=1.0*anx/n;any=1.0*any/n;simulate();printf("%.3lf %.3lf",anx,any);
}模擬退火對于我這種noip狗肯定是不會考
但是多一個偏分的技巧不是很好嗎
隨機化
隨機化運用在搜索中，枚舉中。在運行次數足夠多的情況下，可以有效避免貪心的錯誤，即使使用了貪心
07年noip的寶藏。
就可以使用這種方法騙分。
運行一次prim的時間很短，我們可以多次運行
我們在使用優先隊列選邊時，可以rand出一個概率來
然后再根據概率加進我們的生成樹中去
)
