题解 P3936 【Coloring】

· · 题解

纯粹模拟退火！！

感谢：我的好盆友：超級·考場WA怪帮我纠正了某些错误

题外话:

这道题其实比较好做的，但是我用小号交了90遍才过

不信可以去看，小号：模拟退火

P3936题面

开始乱搞讲思路：

1.按照题目要求先建一个有顺序的图，求出q

那样例打比方：

输入：

2 3 3

1 2 2

我们可以按照顺序建图当然你也可以随机建图

按顺序建图后为：

1 2 2
3 3 3

代码：

void getmap()
{
    int x=1,y=1;
    for(int i=1;i<=c;i++)
    {
        while(color[i]--)
        {
            g[x][y]=i;
            nowg[x][y]=i;   
            if(y==m)
            {
                x++;
                y=1;
            }
            else
                y++;
        }
    }
}

2.就可以开始随意乱搞玄学模拟退火了

如果对模拟退火不理解的话不理解你也不会来这里吧，我推荐去看看2018年洛谷日报索引 里面的模拟退火算法

如果没AC的话，就试试换换参数吧，我就是这样试过来的qwq

下面贴没有剪枝但是开O3才AC了的代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#pragma GCC optimize(3)
using namespace std;
int g[25][25],color[55],nowg[25][25];
int n,m,c,ansq,older;
int getq()
{
    int sum=0;
    for(int i=1;i<n;i++)
        for(int j=1;j<m;j++)
        {
            if(nowg[i][j]!=nowg[i][j+1])
                sum++;
            if(nowg[i][j]!=nowg[i+1][j])
                sum++;
        }
    for(int i=1;i<m;i++)
        if(nowg[n][i]!=nowg[n][i+1])
            sum++;
    for(int i=1;i<n;i++)
        if(nowg[i][m]!=nowg[i+1][m])
            sum++;
    return sum;
}
void getmap()
{
    int x=1,y=1;
    for(int i=1;i<=c;i++)
    {
        while(color[i]--)
        {
            g[x][y]=i;
            nowg[x][y]=i;   
            if(y==m)
            {
                x++;
                y=1;
            }
            else
                y++;
        }
    }
}
void cpy()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
        //  printf("%d ",nowg[i][j]);
            g[i][j]=nowg[i][j];
        }
        //printf("\n");
    }
}
void cpy1()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
        //  printf("%d ",nowg[i][j]);
            nowg[i][j]=g[i][j];
        }
        //printf("\n");
    }
}
void monituihuo()
{
    double T=1,deita=0.99999,T_min=1e-5;
    older=ansq;
    while(T>T_min)
    {
        int x1=(rand()%(n))+1;
        int y1=(rand()%(m))+1;
        int x2=(rand()%(n))+1;
        int y2=(rand()%(m))+1;
        int huan=nowg[x1][y1];
        nowg[x1][y1]=nowg[x2][y2];
        nowg[x2][y2]=huan;
        int ans_now=getq();
        double de=ans_now-older;
        if((de<0)||(exp(-de/T)*RAND_MAX>((rand()%1000000)/1000000.0)))
            older=ans_now;
        else
            cpy1();
        if(older<=ansq)
        {
            ansq=older;
            cpy();
        }
        T*=deita;
    }   
}
int main()
{
    srand(107.77777777);
    srand(rand());
    scanf("%d%d%d",&n,&m,&c);
    for(int i=1;i<=c;i++)
        scanf("%d",&color[i]);
    getmap();
    ansq=getq();
    older=ansq;
/*  for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            printf("%d ",nowg[i][j]);
        printf("\n");
    }*/
    for(int i=1;i<=3;i++)
        monituihuo();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            printf("%d ",g[i][j]);
        cout<<endl;
    }
    //cout<<ansq<<endl;
    return 0;
}

如果觉得有用的话，让我看到你们的赞qwq