萌新刚学退火,来刷退火之题。调参整人心态,发帖求助大佬。
  • 板块P3936 Coloring
  • 楼主STUDENT00
  • 当前回复10
  • 已保存回复10
  • 发布时间2023/1/1 20:04
  • 上次更新2023/10/24 05:52:27
查看原帖
萌新刚学退火,来刷退火之题。调参整人心态,发帖求助大佬。
658786
STUDENT00楼主2023/1/1 20:04

提交了将近一页,分数始终恒定在63-65。

代码里加了一些注释:

#include<bits/stdc++.h>
#define y1 _y
#define N 25
#define M 55
using namespace std;
int n,m,c,p[M],a[N][N],ans[N][N],anss=1e9;
int func(){
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(i<n&&a[i][j]!=a[i+1][j]) ans++;
			if(j<m&&a[i][j]!=a[i][j+1]) ans++;
		}
	}
	return ans;
}
void solve(){
	double T=1e7,eps=1e-8,delta=0.98;
	while(T>eps){
		if((double)clock()/CLOCKS_PER_SEC>0.95) break;
		int x1,y1,x2,y2;
		do{x1=rand()%n+1;y1=rand()%m+1;x2=rand()%n+1;y2=rand()%m+1;}while(x1==x2&&y1==y2); //将(x1,y1)和(x2,y2)交换
		swap(a[x1][y1],a[x2][y2]);
		int now=func(),dE=now-anss;
		if(dE<0){
			for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ans[i][j]=a[i][j];
			anss=now;
		}else if(exp(-dE/T)<=(double)rand()/RAND_MAX) swap(a[x1][y1],a[x2][y2]); //更新答案
		T*=delta; 
	}
}
int main(){
	srand(time(0));
	scanf("%d%d%d",&n,&m,&c);
	for(int i=1;i<=c;i++) scanf("%d",&p[i]);
	int k=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			while(!p[k]) k++;
			a[i][j]=k;p[k]--;
		}
	}  //顺次填色
	while((double)clock()/CLOCKS_PER_SEC<0.95) solve(); //模拟退火
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) printf("%d ",ans[i][j]);
		printf("\n");
	}
	return 0;
}
2023/1/1 20:04
加载中...