2018-05-11 12:44:58

## Code

// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
using namespace std;
int N,M,C,p[51];
int A[25][25],E[51],out[25][25];
int sum,ans=1000000;
int Get(int x,int y)
{
int Ans=0;
if(A[x][y]!=A[x-1][y]) Ans++;
if(A[x][y]!=A[x+1][y]) Ans++;
if(A[x][y]!=A[x][y-1]) Ans++;
if(A[x][y]!=A[x][y+1]) Ans++;
return Ans;
}
void Update(int k)
{
if(ans<=k) return;
ans=k;
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
out[i][j]=A[i][j];
}
double Rand(){return 1.0*(rand()%100000000)/100000000;}
int Rand(int x){return rand()%x+1;}
void SA(double T)
{
while(T>1e-15)
{
T*=0.99999;
int x1=Rand(N),x2=Rand(N);
int y1=Rand(M),y2=Rand(M);
int p=sum;
p-=Get(x1,y1)+Get(x2,y2);
swap(A[x1][y1],A[x2][y2]);
p+=Get(x1,y1)+Get(x2,y2);
if(p<sum||exp((sum-p)/T)>Rand()) {Update(sum=p);continue;}
swap(A[x1][y1],A[x2][y2]);
}
}
int main()
{
srand(19260817233);
cin>>N>>M>>C;
for(int i=1;i<=C;i++) cin>>p[i];
int T=5;
while(T--)
{
for(int i=1;i<=C;i++) E[i]=p[i];
for(int i=1;i<=N;i++)
for(int j=1,x=1;j<=M;j++)
{
x=rand()%C+1;
while(!E[x]) x=rand()%C+1;
A[i][j]=x; E[x]--;
}
sum=0;
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
sum+=Get(i,j);
Update(sum);SA(100000000);
}
for(int i=1;i<=N;i++,puts(""))
for(int j=1;j<=M;j++)
printf("%d ",out[i][j]);
return 0;
}
//之前这里一个错误找了一周：定义了一个B存该点贡献，但是交换的话应该改动10个B
//而我只改了2个，把贡献算成负数，但是somehowAC了


• star
首页