題意：　
? ? ?? gty又虐了一場(chǎng)比賽，被虐的蒟蒻們決定吊打gty。
　　gty見大勢(shì)不好機(jī)智的分出了n個(gè)分身，但還是被人多勢(shì)眾的蒟蒻抓住了。
　　蒟蒻們將n個(gè)gty吊在n根繩子上，每根繩子穿過天臺(tái)的一個(gè)洞。這n根繩子有一個(gè)公共的繩結(jié)x。
　　吊好gty后蒟蒻們發(fā)現(xiàn)由于每個(gè)gty重力不同，繩結(jié)x在移動(dòng)。
　　蒟蒻wangxz腦洞大開的決定計(jì)算出x最后停留處的坐標(biāo)，由于他太弱了決定向你求助。
　　不計(jì)摩擦，不計(jì)能量損失，由于gty足夠矮所以不會(huì)掉到地上。
輸入第一行為一個(gè)正整數(shù)n，表示gty的數(shù)目。
接下來n行,每行三個(gè)整數(shù)xi，yi，wi，表示第i個(gè)gty的橫坐標(biāo)，縱坐標(biāo)和重力。
對(duì)于20%的數(shù)據(jù)，gty排列成一條直線。

輸出1行兩個(gè)浮點(diǎn)數(shù)（保留到小數(shù)點(diǎn)后3位），表示最終x的橫、縱坐標(biāo)。
對(duì)于50%的數(shù)據(jù)，1<=n<=1000。對(duì)于100%的數(shù)據(jù)，1<=n<=10000,-100000<=xi,yi<=100000 (p:最大數(shù)據(jù)就是初始溫度范圍)

?技巧：這種時(shí)候我們可以試著先本機(jī)跑跑自造數(shù)據(jù)看看精度怎么樣.
如果發(fā)現(xiàn)經(jīng)常陷入局部最優(yōu)解的話考慮增大 初始溫度(T0) 和 降溫系數(shù)(d)(會(huì)增加時(shí)間復(fù)雜度)
如果發(fā)現(xiàn)最終精度不夠的話考慮減小 最終溫度(Tk)
這個(gè)博客不錯(cuò):
https://www.cnblogs.com/rvalue/p/8678318.html
網(wǎng)上的那個(gè)根據(jù)一定的概率采納新解的隨機(jī)函數(shù)好像是假的。

#include<bits/stdc++.h> #define mp make_pair #define sz(x) int((x).size()) #define fin freopen("in.txt","r",stdin) #define fout freopen("out.txt","w",stdout) #define io ios::sync_with_stdio(0),cin.tie(0) using namespace std; typedef long long ll; typedef pair<int,int> PII; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int maxn = 1e4 + 5; int n,x,y; struct point { double x,y,w; } p[maxn],now,nex,ansp; double dis(point a,point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double f(point x) { //評(píng)估函數(shù)double res = 0;for (int i=1;i<=n;i++) res+=dis(x,p[i])*p[i].w;return res; } double ans=1e111;//最開始的能量值,初始很大就可以,不用修改 void sa() {double T=1e5; //初始溫度, (可以適當(dāng)修改,最好和給的數(shù)據(jù)最大范圍相同,或者縮小其原來0.1)double d=0.95; //降溫系數(shù) (可以適當(dāng)修改,影響結(jié)果的精度和循環(huán)的次數(shù),)double eps=1e-4; //最終溫度 (要是因?yàn)榫葐栴}，可以適當(dāng)減小最終溫度)double TT=0.8; //采納新解的初始概率double dd=0.996; //(可以適當(dāng)修改,采納新解變更的概率)(這個(gè)概率下面新解更新的時(shí)候,最好和未采納的新解更新的次數(shù)是一半一半)double res=f(now); //傳入的初始默認(rèn)解(now)下得到的評(píng)估能量值if (res<ans) ans=res,ansp=now;//ansp終解while (T>eps){for (int i=-1;i<=1;++i)for (int j=-1;j<=1;++j)if (i||j){nex.x=now.x+T*i,nex.y=now.y+T*j;//新解double tmp=f(nex);//新解下的評(píng)估能量值if (tmp<ans) ans=tmp,ansp=nex;//降溫成功,更新當(dāng)前最優(yōu)解if (tmp<res) res=tmp,now=nex;// 降溫成功,采納新解else if (TT>rand()%10000/10000.0) res=tmp,now=nex;//,cout<<"======"<<endl;//沒有 降溫成功，但是以一定的概率采納新解//else cout<<"="<<endl;//用于測(cè)試，設(shè)定的采納新解的概率,是否為一半一半,可以適當(dāng)修改降溫參數(shù)dd}T*=d; TT*=dd;} } int main() {srand(time(0));scanf("%d",&n);for (int i=1;i<=n;++i) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].w),now.x+=p[i].x,now.y+=p[i].y;now.x/=n,now.y/=n; sa();printf("%.3f %.3f\n",ansp.x,ansp.y);return 0; }

?

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的Bzoj 3680 吊打xxx【[模拟退火】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。