题解 P3936 【Coloring】
xzyxzy
2018-05-11 12:44:58
### 模拟退火
#### 这里有一个搜索专讲的[课件](http://www.cnblogs.com/xzyxzy/p/8546384.html)?(预计2018暑假之前完成吧，大家可以看一看，也许不是以课件的形式呈现)
思路就是rand一个答案，然后退火地交换，直到最优
计算贡献用另外一种方便点的方式：每个点往四周算，那么方格内的贡献被算两次，边界上被算一次，但是不影响
## Code
```cpp
// 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了
```
## 不保证程序能一遍AC(你也看到了是完全随机的随机种子)
~~另外我很迷的地方是这个now（贡献）算到最后是负数。。~~
~~有没有大佬能教教我QAQ~~
好的找到原因了Upd:7.18