求救 调了两个半小时了quq
  • 板块P3936 Coloring
  • 楼主LYY_yyyy
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/11/9 11:32
  • 上次更新2023/10/27 03:39:37
查看原帖
求救 调了两个半小时了quq
466451
LYY_yyyy楼主2022/11/9 11:32

Code:

#include<bits/stdc++.h>
#define double long double
using namespace std;
int n,m,c;
int ans;
int co[10101]; 
int mapp[101][101];
int anss[101][101];
int calc()
{
	int q=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(i!=n&&mapp[i+1][j]!=mapp[i][j]) q++;
			if(j!=m&&mapp[i][j+1]!=mapp[i][j]) q++;
		}
	}
	return q;
}

void SA()
{
	memcpy(mapp, anss, sizeof(anss));
	for(double T=300;T>=1e-14;T*=0.991)
	{
		if((double)clock()/CLOCKS_PER_SEC>4.8) return ;
		int x1=rand()%n+1,y1=rand()%m+1,x2=rand()%n+1,y2=rand()%m+1;
		while(mapp[x1][y1]==mapp[x2][y2]) x1=(int)rand()%n+1,y1=(int)rand()%m+1,x2=(int)rand()%n+1,y2=(int)rand()%m+1;
		//cout<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<' ';
		swap(mapp[x1][y1],mapp[x2][y2]);
		int nowans=calc();
		double del=nowans-ans;
		
		//cout<<del<<endl;
		//cout<<-del/T<<endl;
		//cout<<exp(-del/T)<<endl;
		if(del<0) 
		{
			ans=nowans;	
			for(int i=1;i<=n;i++)
			{
				for(int j=1;j<=m;j++) anss[i][j]=mapp[i][j];
			}
			//cout<<ans<<' '<<x1<<' '<<y1<<' '<<x2<<' '<<y2<<' '<<endl;
		}
		else if(exp(-del/T)*RAND_MAX<=rand()) swap(mapp[x1][y1],mapp[x2][y2]);
	}
}
int main()
{
	srand(20081007);
	cin>>n>>m>>c;
	for(int i=1;i<=c;i++) cin>>co[i];
	int cnt=co[1],now=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			mapp[i][j]=now;
			cnt--;
			if(cnt==0)
				cnt=co[++now];
		}
	}
	ans=calc();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++) anss[i][j]=mapp[i][j];
	}
	SA();SA();SA();SA();SA();
	//cout<<ans<<endl;
	//cout<<calcc()<<endl;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++) cout<<anss[i][j]<<' ';
		cout<<endl;
	}
	return 0;
}
2022/11/9 11:32
加载中...