P2210 Haywire

模拟退火练手题

#include<cmath>
#include<ctime>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=;
int n,res,no[N],b[N];bool g[N][N];
inline int check(){
res=;
for(int i=;i<=n;i++) b[no[i]]=i;
for(int i=;i<=n;i++){
for(int j=;j<i;j++){
if(g[i][j]){
res+=abs(b[i]-b[j]);
}
}
}
return res;
}
int main(){
srand(time()),srand(rand()+);
scanf("%d",&n);
for(int i=,x,y,z;i<=n;i++) scanf("%d%d%d",&x,&y,&z),g[i][x]=g[i][y]=g[i][z]=;
for(int i=;i<=n;i++) no[i]=i;
int best=check();
for(int it=;it--;){
for(double T=1e6;T>=1e-;T*=0.99){
int x=rand()%n+,y=rand()%n+;
for(;x==y;y=rand()%n+);
swap(no[x],no[y]);
int tmp=check();
if(tmp<best) best=tmp;
else if(exp((best-tmp)/T)*RAND_MAX<rand()) swap(no[x],no[y]);
}
}
printf("%d\n",best);
return ;
}

最新文章

  1. kindeditor-4.1.3工具使用技巧:如何在编辑区上传图片并保存绝对路径
  2. 一个解决adb5037端口被绑定问题的小程序-以管理员身份运行
  3. JS:操作样式表1:行内样式
  4. Python基础(9)--正则表达式
  5. Power Gating的设计(架构)
  6. iOS开发 Date转字符串
  7. Java中的代码块
  8. 如何在ubuntu下安装合适的翻译词典
  9. KVC, KVO实现原理剖析
  10. UniqueID和ClientID的来源
  11. Android屏幕适配与切图_汇总
  12. Qt学习一门:直接使用QT具
  13. 【C语言探索之旅】 第二部分第七课:文件读写
  14. Spring环境配置
  15. JavaScript基础精讲
  16. springboot中访问jsp文件方式
  17. 【leetcode】448. Find All Numbers Disappeared in an Array
  18. (转)python 判断数据类型
  19. PostgreSQL的 PITR实战---运用 recovery_target_time
  20. angularjs基础——控制器

热门文章

  1. 谈谈MySQL中的锁
  2. koa2---koa-bodyparser中间件
  3. Java 之 Cookie
  4. docker中基于centos镜像部署lnmp环境 php7.3 mysql8.0 最新版
  5. MySQL Percona Toolkit--pt-osc学习
  6. 定时任务模块——APScheduler
  7. linux系统中如何查看最后一封mail
  8. linux下安装cryptography兼论查找合适pip的whl文件技巧
  9. httprunner学习1-环境与登录接口案例
  10. Django之路——11 Django用户认证组件 auth