Luogu7218 [JOISC2020] 伝説の団子職人
提交答案、匈牙利、随机化、贪心
先给出一种贪心,也就是模仿匈牙利的过程进行增广,枚举一个非\(W\)点,再枚举一个\(W\),如果对面的那个团子恰好符合要求,增广成功,否则像匈牙利一样增广。
然后进行随机化调整,每次以一定概率撤销使用过的\(W\),重新增广,如果比答案优则更新。注意跑得越久,撤销概率越小,类似模拟退火。
跑各组数据的代码基本相同,下面是跑第一组数据的代码。
\(Code:\)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define N 505
#define pr pair<int,int>
#define mp make_pair
#define ll long long
#define db double
using namespace std;
const int lim=47220;
db alpha=0.95;
int n,m,cnt,ans,rans;
char a[N][N],b[N][N];
pr e[N*N];
int dic[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1}};
char ch[8]={'-','-','|','|','\\','\\','/','/'};
int mch[N][N][2],rch[N][N][2];
ll tim,vis[N][N];
mt19937 mt(time(NULL));
bool ok(int x,int y)
{
return x>=1 && x<=n && y>=1 && y<=m;
}
bool dfs(int x,int y)
{
if (vis[x][y]==tim)
return false;
vis[x][y]=tim;
char c(a[x][y]);
c=(c=='P')?'G':'P';
for (int i=0;i<8;++i)
{
int nx(x+dic[i][0]),ny(y+dic[i][1]);
int zx(nx+dic[i][0]),zy(ny+dic[i][1]);
if (!ok(zx,zy) || a[nx][ny]!='W' || a[zx][zy]!=c)
continue;
a[nx][ny]=ch[i];
if (!mch[zx][zy][0] || dfs(mch[zx][zy][0],mch[zx][zy][1]))
{
if (mch[zx][zy][0])
{
for (int j=0;j<8;++j)
{
int tx(zx+(dic[j][0] << 1)),ty(zy+(dic[j][1] << 1));
if (!ok(tx,ty))
continue;
if (mch[zx][zy][0]==tx && mch[zx][zy][1]==ty)
{
a[zx+dic[j][0]][zy+dic[j][1]]='W';
break;
}
}
}
mch[x][y][0]=zx,mch[x][y][1]=zy;
mch[zx][zy][0]=x,mch[zx][zy][1]=y;
return true;
}
a[nx][ny]='W';
}
return false;
}
int main()
{
freopen("01.in","r",stdin);
freopen("01.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i)
{
scanf("%s",a[i]+1);
for (int j=1;j<=m;++j)
if (a[i][j]!='W')
e[++cnt]=mp(i,j);
}
for (int i=1;i<=cnt;++i)
if (!mch[e[i].first][e[i].second][0])
++tim,ans+=dfs(e[i].first,e[i].second);
int T(0);
while (ans<lim)
{
++T;
if (T%500==0)
alpha*=1.00050,cerr << ans << endl;
alpha=min(alpha,0.9999);
memcpy(b,a,sizeof(a)),rans=ans;
memcpy(rch,mch,sizeof(mch));
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
if (a[i][j]!='P' && a[i][j]!='G' && a[i][j]!='W')
{
if ((db)mt()/4294967295>alpha)
{
int t;
if (a[i][j]=='-')
t=0; else
if (a[i][j]=='|')
t=2; else
if (a[i][j]=='\\')
t=4; else
t=6;
int nx(i-dic[t][0]),ny(j-dic[t][1]);
int zx(i+dic[t][0]),zy(j+dic[t][1]);
mch[nx][ny][0]=mch[nx][ny][1]=0;
mch[zx][zy][0]=mch[zx][zy][1]=0;
a[i][j]='W';
--ans;
}
}
shuffle(e+1,e+cnt+1,mt);
for (int i=1;i<=cnt;++i)
if (!mch[e[i].first][e[i].second][0])
++tim,ans+=dfs(e[i].first,e[i].second);
if (ans<rans)
{
ans=rans;
memcpy(a,b,sizeof(b));
memcpy(mch,rch,sizeof(rch));
}
}
for (int i=1;i<=n;++i)
printf("%s\n",a[i]+1);
return 0;
}