首页 > 代码库 > POJ 2420 A Star not a Tree? (模拟退火)
POJ 2420 A Star not a Tree? (模拟退火)
题目地址:POJ 2420
今天在比赛遇到了这题。。于是现场学了一下模拟退火。。。。
这题是先初始化为一个点,然后不断趋近距离和最短的点。还是挺简单的。。
代码如下:
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <stdlib.h> #include <math.h> #include <ctype.h> #include <queue> #include <map> #include <set> #include <algorithm> using namespace std; #define LL __int64 const int INF=0x3f3f3f3f; int n; struct point { int x, y; }dian[200]; double dist(point a, point b) { return sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y)); } double juhe(point x) { int i; double z=0; for(i=0;i<n;i++) { z+=dist(x,dian[i]); } return z; } int main() { int i, j, flag, step; point st, ed; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d%d",&dian[i].x,&dian[i].y); } step=100; st.x=0;st.y=0; double d=juhe(st), s; while(step>0.2) { flag=1; while(flag) { flag=0; point now; now.x=st.x+step; now.y=st.y; s=juhe(now); if(d>s) { flag=1; d=s; ed=now; } now.x=st.x-step; now.y=st.y; s=juhe(now); if(d>s) { flag=1; d=s; ed=now; } now.x=st.x; now.y=st.y+step; s=juhe(now); if(d>s) { flag=1; d=s; ed=now; } now.x=st.x; now.y=st.y-step; s=juhe(now); if(d>s) { flag=1; d=s; ed=now; } if(flag) st=ed; } step/=2.0; } printf("%.0f\n",d); return 0; }
POJ 2420 A Star not a Tree? (模拟退火)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。