P7218 [JOISC2020] 伝説の団子職人

· · 题解

P7218 [JOISC2020] 伝説の団子職人

模拟退火真的是太好玩了！

upd：发现原程序实际上是一份爬山，现添加说明并补充模拟退火代码。

upd:取消了 NP-Hard 的 LaTeX。

题意这里不再赘述

P7218 [JOISC2020] 伝説の団子職人

做法分析

我们可以看出这个问题可以转化成一般图的最大独立集。

即我们把几串共用了相同位置的丸子连边，表示它们不能同时存在，于是这个问题就转化完成了。

我们知道这是个 NP-Hard 问题，那就需要考虑模拟退火。

先按一串一串地把图建好。然后退火过程中，每次选一个没选的点，选中它并退掉与它相连的已选中的点，并更新与退掉的点相连的那些点（这一步很重要不然答案越跑越劣）。

然后前面几篇题解是用数据结构维护没选的点每次随机排名，实际上直接纯随就可以，一直随直到随到一个没选的点，实测命中率还是相当高的。

建图

这里是考虑每个中间的 W，分别讨论四个方向。只要保证两边都不是 W 并且不同即可。

对于连边这里在每个点上开了个 vector 存包含该点串的编号。

（似乎是现有题解区里最短的代码了）

调参

这个玩意调了我一上午，主要是模拟退火要保证接受劣解的概率不要太高，实在不行给 d 乘上一个系数 k 来放大代价，不然就会越跑越劣甚至干不过爬山。模拟退化算法

因为后来发现通过的实际上已经退化成了爬山，所以这里不再给出所有的参数，仅放出第五个点相对较优的参数：

#5:T=6,dta=0.999995,k=16

不知道为什么爬山能过，所以这里放出两份代码。

贴代码

爬山：

#include <bits/stdc++.h>
#define lint long long
using namespace std;
inline int read(){
    char c;int f=1,res=0;
    while(c=getchar(),!isdigit(c))if(c=='-')f*=-1;
    while(isdigit(c))res=res*10+c-'0',c=getchar();
    return res*f;
}
const int N=505,P=N*N*8;
int hed[P],nxt[P],ver[P],cnt=1;
inline void ae(int u,int v){
    ver[++cnt]=v;
    nxt[cnt]=hed[u];
    hed[u]=cnt;
}
inline void lnk(int u,int v)
    {ae(u,v);ae(v,u);}
vector<int> ex[N][N];
int d[4][2]={{0,1},{1,0},{1,1},{1,-1}};
char c[4]={'-','|','\\','/'};
struct pnt{int x,y,d;}p[P];
int n,m,tot=0;char s[N][N];
inline void inst(int x,int y,int dir){//加点 
    int x0=x+d[dir][0],y0=y+d[dir][1];
    int x1=x-d[dir][0],y1=y-d[dir][1];
    if(x0<1||y0<1||x1<1||y1<1)return;
    if(x0>n||x1>n||y0>m||y1>m)return;
    if(s[x0][y0]=='W'||s[x1][y1]=='W')
        return;
    if(s[x][y]!='W'||s[x0][y0]==s[x1][y1])
        return;
    int u=++tot;p[u]=pnt{x,y,dir};
    for(int v:ex[x][y])lnk(u,v);ex[x][y].push_back(u);
    for(int v:ex[x0][y0])lnk(u,v);ex[x0][y0].push_back(u);
    for(int v:ex[x1][y1])lnk(u,v);ex[x1][y1].push_back(u);
}
inline void build(){//建图 
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            for(int k=0;k<4;++k)
                inst(i,j,k);
}
int ans;
bitset<P> vis,_vis,avis;
inline bool ck(int u){//判断当前点能否选 
    if(_vis[u])return false;
    for(int e=hed[u];e;e=nxt[e])
        if(_vis[ver[e]])return false;
    return true;
}
inline int calc(){//产生初始解 
    int res=0;
    for(int u=1;u<=tot;++u)
        if(ck(u))_vis[u]=1,++res;
    return res;
}
inline int rnd(int md)
    {return 1ll*rand()*rand()%md+1;}
inline int del(int u){
    _vis[u]=0;int res=0;
    for(int e=hed[u];e;e=nxt[e])
        if(ck(ver[e]))_vis[ver[e]]=1,++res;
    return res;
}
inline int upd(){//产生新解 
    _vis=vis;
    int res=0,t=0;
    while(++t<=10){//没什么用的防死循环 
        int u=rnd(tot);
        if(_vis[u])continue;
        _vis[u]=1;++res;
        for(int e=hed[u];e;e=nxt[e]){
            int v=ver[e];
            if(_vis[v])res+=del(v)-1;
            //退掉与u相连的v并更新与v相连的点 
        }break;
    }return res;
}
inline void SA(){
    ans=calc();vis=_vis;
    int res=ans,_res;
    double T=0.01,dta=0.999999,k=16;
    while(ans<48620){
        _res=res+upd();
        if(_res>ans)//也许这里不是比较全局答案，但好像这样跑得快些 
            avis=vis=_vis,ans=res=_res,cout<<T<<" "<<ans<<endl;
        else if(exp(k*(_res-ans)/T)*RAND_MAX>rand())
            vis=_vis,res=_res;
        T*=dta;
    }
}
int main(){
    freopen("05.in","r",stdin);
    n=read();m=read();
    for(int i=1;i<=n;++i)
        scanf("%s",s[i]+1);
    build();SA();
    for(int i=1;i<=tot;++i)
        if(avis[i])
            s[p[i].x][p[i].y]=c[p[i].d];
    freopen("05.ans","w",stdout);
    for(int i=1;i<=n;++i)
        printf("%s\n",s[i]+1);
    return 0;
}

模拟退火：

#include <bits/stdc++.h>
#define lint long long
using namespace std;
inline int read(){
    char c;int f=1,res=0;
    while(c=getchar(),!isdigit(c))if(c=='-')f*=-1;
    while(isdigit(c))res=res*10+c-'0',c=getchar();
    return res*f;
}
const int N=505,P=N*N*8;
int hed[P],nxt[P],ver[P],cnt=1;
inline void ae(int u,int v){
    ver[++cnt]=v;
    nxt[cnt]=hed[u];
    hed[u]=cnt;
}
inline void lnk(int u,int v)
    {ae(u,v);ae(v,u);}
vector<int> ex[N][N];
int d[4][2]={{0,1},{1,0},{1,1},{1,-1}};
char c[4]={'-','|','\\','/'};
struct pnt{int x,y,d;}p[P];
int n,m,tot=0;char s[N][N];
inline void inst(int x,int y,int dir){//加点 
    int x0=x+d[dir][0],y0=y+d[dir][1];
    int x1=x-d[dir][0],y1=y-d[dir][1];
    if(x0<1||y0<1||x1<1||y1<1)return;
    if(x0>n||x1>n||y0>m||y1>m)return;
    if(s[x0][y0]=='W'||s[x1][y1]=='W')
        return;
    if(s[x][y]!='W'||s[x0][y0]==s[x1][y1])
        return;
    int u=++tot;p[u]=pnt{x,y,dir};
    for(int v:ex[x][y])lnk(u,v);ex[x][y].push_back(u);
    for(int v:ex[x0][y0])lnk(u,v);ex[x0][y0].push_back(u);
    for(int v:ex[x1][y1])lnk(u,v);ex[x1][y1].push_back(u);
}
inline void build(){//建图 
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            for(int k=0;k<4;++k)
                inst(i,j,k);
}
int ans;
bitset<P> vis,_vis,avis;
inline bool ck(int u){//判断当前点能否选 
    if(_vis[u])return false;
    for(int e=hed[u];e;e=nxt[e])
        if(_vis[ver[e]])return false;
    return true;
}
inline int calc(){//产生初始解 
    int res=0;
    for(int u=1;u<=tot;++u)
        if(ck(u))_vis[u]=1,++res;
    return res;
}
inline int rnd(int md)
    {return 1ll*rand()*rand()%md+1;}
inline int del(int u){
    _vis[u]=0;int res=0;
    for(int e=hed[u];e;e=nxt[e])
        if(ck(ver[e]))_vis[ver[e]]=1,++res;
    return res;
}
inline int upd(){//产生新解 
    _vis=vis;
    int res=0,t=0;
    while(++t<=10){//没什么用的防死循环 
        int u=rnd(tot);
        if(_vis[u])continue;
        _vis[u]=1;++res;
        for(int e=hed[u];e;e=nxt[e]){
            int v=ver[e];
            if(_vis[v])res+=del(v)-1;
            //退掉与u相连的v并更新与v相连的点 
        }break;
    }return res;
}
inline void SA(){
    ans=calc();vis=_vis;
    int res=ans,_res;
    double T=6,dta=0.999995,k=16;
    while(ans<48620){
        _res=res+upd();
        if(_res>=res){
            if(_res>ans)
                ans=_res,avis=_vis,cout<<T<<" "<<_res<<endl;
            vis=_vis;res=_res;
        }else if(exp(k*(_res-res)/T)*2e9>rnd(2e9))
            vis=_vis,res=_res;
        T*=dta;
    }
}
int main(){
    ios::sync_with_stdio(false);
    freopen("05.in","r",stdin);
    n=read();m=read();
    for(int i=1;i<=n;++i)
        scanf("%s",s[i]+1);
    build();SA();
    for(int i=1;i<=tot;++i)
        if(avis[i])
            s[p[i].x][p[i].y]=c[p[i].d];
    freopen("05.ans","w",stdout);
    for(int i=1;i<=n;++i)
        printf("%s\n",s[i]+1);
    return 0;
}