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