P7218 [JOISC2020] 伝説の団子職人
SDNetFriend
2021-11-26 15:00:48
## P7218 [JOISC2020] 伝説の団子職人
~~模拟退火真的是太好玩了！~~
upd：发现原程序实际上是一份爬山，现添加说明并补充模拟退火代码。
upd:取消了 NP-Hard 的 LaTeX。
### 题意这里不再赘述
[P7218 [JOISC2020] 伝説の団子職人](https://www.luogu.com.cn/problem/P7218)
### 做法分析
我们可以看出这个问题可以转化成一般图的最大独立集。
即我们把几串共用了相同位置的丸子连边，表示它们不能同时存在，于是这个问题就转化完成了。
我们知道这是个 NP-Hard 问题，那就需要考虑模拟退火。
先按一串一串地把图建好。然后退火过程中，每次选一个没选的点，选中它并退掉与它相连的已选中的点，**并更新与退掉的点相连的那些点**（这一步很重要不然答案越跑越劣）。
然后前面几篇题解是用数据结构维护没选的点每次随机排名，实际上直接纯随就可以，一直随直到随到一个没选的点，实测命中率还是相当高的。
### 建图
这里是考虑每个中间的 `W`，分别讨论四个方向。只要保证两边都不是 `W` 并且不同即可。
对于连边这里在每个点上开了个 `vector` 存包含该点串的编号。
（似乎是现有题解区里最短的代码了）
### 调参
这个玩意调了我一上午，主要是模拟退火要保证接受劣解的概率不要太高，实在不行给 $d$ 乘上一个系数 $k$ 来放大代价，不然就会越跑越劣甚至干不过爬山。~~模拟退化算法~~
因为后来发现通过的实际上已经退化成了爬山，所以这里不再给出所有的参数，仅放出第五个点相对较优的参数：
`#5:T=6,dta=0.999995,k=16`
不知道为什么爬山能过，所以这里放出两份代码。
### 贴代码
#### 爬山：
```cpp
#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;
}
```
#### 模拟退火：
```cpp
#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;
}
```