题解 P3936 【Coloring】

2018-05-11 12:44:58


模拟退火

这里有一个搜索专讲的课件?(预计2018暑假之前完成吧,大家可以看一看,也许不是以课件的形式呈现)

思路就是rand一个答案,然后退火地交换,直到最优

计算贡献用另外一种方便点的方式:每个点往四周算,那么方格内的贡献被算两次,边界上被算一次,但是不影响

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了

不保证程序能一遍AC(你也看到了是完全随机的随机种子)

另外我很迷的地方是这个now(贡献)算到最后是负数。。

有没有大佬能教教我QAQ

好的找到原因了Upd:7.18