首页 > 其他 > 详细

P2210 Haywire

时间:2019-08-12 20:42:27      阅读:102      评论:0      收藏:0      [点我收藏+]

P2210 Haywire

 模拟退火练手题

#include<cmath>
#include<ctime>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=30;
int n,res,no[N],b[N];bool g[N][N];
inline int check(){
    res=0;
    for(int i=1;i<=n;i++) b[no[i]]=i;
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            if(g[i][j]){
                res+=abs(b[i]-b[j]);
            }
        }
    }
    return res;
}
int main(){
    srand(time(0)),srand(rand()+20000329);
    scanf("%d",&n);
    for(int i=1,x,y,z;i<=n;i++) scanf("%d%d%d",&x,&y,&z),g[i][x]=g[i][y]=g[i][z]=1;
    for(int i=1;i<=n;i++) no[i]=i;
    int best=check();
    for(int it=437;it--;){
        for(double T=1e6;T>=1e-14;T*=0.99){
            int x=rand()%n+1,y=rand()%n+1;
            for(;x==y;y=rand()%n+1);
            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 0;
}

 

P2210 Haywire

原文:https://www.cnblogs.com/shenben/p/11342208.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!