钥匙题专项训练

· · 个人记录

钥匙-锁模型专项训练

同学们，我们来练习一下这个钥匙-锁模型咩！

上次我给大家上了一堂转转课做了个铺垫，那么今天我们就来学习几道例题再来巩固一下咩！钥匙题是目前考试的热门考点哈！要保证考试遇到这种题目的时候我们不能吃亏哈！

热身题：CF830A 办公室钥匙

题目描述

有 n 个师傅忘撇钥匙，给出所有师傅的坐标 a，k 串钥匙的坐标 b 以及工地的坐标 p，可以让任意一个师傅跑去撇任意一串钥匙回工地来开锁，师傅都是一秒走一格，所有师傅同时移动，问最少多长时间才能都进工地。

题解

这道题还是相当基础的得咩。我们把师傅些跟钥匙排个序，设 dp_{i,j} 表示考虑前 i 个师傅和前 j 串钥匙的最小总时间。考虑 i 师傅去不去撇钥匙 j 捏？如果去的话总共就会花费 \max\{dp_{i-1,j-1},|a_i-b_j|+|b_j-p|\} 的时间。否则就是 dp_{i,j-1}。则有

dp_{i,j}=\min\{\max\{dp_{i-1,j-1},|a_i-b_j|+|b_j-p|\},dp_{i,j-1}\}

暴力 DP 就做完了得咩。时间复杂度 \mathcal O(n^2)，跑得风快！

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2008,K=2009;
int n,k,p,a[N],b[K],dp[N][K];
int main()
 {
  scanf("%d%d%d",&n,&k,&p);
 for(int i=1;i<=n;++i)scanf("%d",&a[i]);
  for(int i=1;i<=k;++i)scanf("%d",&b[i]);
sort(a+1,a+n+1),sort(b+1,b+k+1);
 for(int i=1;i<2008;++i)
for(int j=0;j<2009;++j)
 {dp[i][j]=2147483647;}
 for(int i=1;i<=n;++i)
   for(int j=1;j<=k;++j)
  {
   dp[i][j]=min(max(dp[i-1][j-1],abs(a[i]-b[j])+abs(b[j]-p)),dp[i][j-1]);
   }
 cout<<dp[n][k];
return 0;
}

ABC273F 第二个锤子

题意：数轴上有 n 个锁，第 i 个锁的位置在 y_i，它的钥匙位置在 z_i，有一个师傅现在在 0 这个位置，他要开车去北京。北京的位置是 X。遇到一串钥匙就可以把它撇到皮带上面以后可以随便用它来开对应的锁。问师傅最短好久能到北京？

分析：这个题还是相当的基础的得咩！就是一个简单的区间 DP 得咩。其实就是一个 089 年的关路灯的模型咩。我们把所有钥匙和锁的位置嗲出来排个序，我们设一个 f_{l,r,0/1} 表示我们已经走完 l\sim r 这些地点的最短时间，现在在 l 还是 r。然后就去往左边和右边扩展，计算一下走出去需要花的时间。能更新的条件就是扩展出来的这个锁它在 [l,r] 的范围里面，因为在范围里面的话它肯定已经经过过并撇在自己的皮带上面了。这样就做完了得咩。跟关路灯一模一样的。相当的规范！

#include <bits/stdc++.h>
using namespace std;
int n,m,x,y[3333],z[3333];
long long f[3333][3333][2],inf=6666666666666;
struct node
 {
  int x,y;
   bool operator<(node b)
   {return x<b.x;
     }
} a[3333];
 int main()
  {scanf("%d%d",&n,&x);
  for(int i=1;i<=n;i++)scanf("%d",&y[i]),a[++m]={y[i],i};
  for(int i=1;i<=n;i++) scanf("%d",&z[i]),a[++m]=(node){z[i],0};
   a[++m]={x,0};
   a[++m]=(node){0,0};
  sort(a+1,a+m+1);
   int wei=0,chu=0;
  for(int i=1;i<=m;i++)
    {if(a[i].x==x)wei=i;
}
 for(int i=1;i<=m;i++)
if(!a[i].x) chu=i;
 for(int i=0;i<3333;i++)
 {for(int j=0;j<3333;j++)
{
   f[i][j][0]=f[i][j][1]=inf; }
  }
 f[chu][chu][0]=f[chu][chu][1]=0;
 for(int len=1;len<m;len++)
for(int l=1;l<=m-len+1;l++)
  {
 int r=l+len-1;
  if(l>1)
   {
 if(a[l-1].y>0&&(z[a[l-1].y]<a[l].x||z[a[l-1].y]>a[r].x)){
 }
  else
   {
f[l-1][r][0]=min(f[l-1][r][0],f[l][r][0]+a[l].x-a[l-1].x);
 f[l-1][r][0]=min(f[l-1][r][0],f[l][r][1]+a[r].x-a[l-1].x);
  }
}
 if(r<m)
  {
  if(a[r+1].y>0&&(z[a[r+1].y]<a[l].x||z[a[r+1].y]>a[r].x))
     ;else
  {f[l][r+1][1]=min(f[l][r+1][1],f[l][r][0]+a[r+1].x-a[l].x);
f[l][r+1][1]=min(f[l][r+1][1],f[l][r][1]+a[r+1].x-a[r].x);}
  }
    }
  long long ans=inf;
 for(int i=1;i<=wei;i++)
{for(int j=wei;j<=m;j++){
  ans=min(ans,min(f[i][j][0],f[i][j][1]));
  }
   }
  if(ans==inf)cout<<-1;
else cout<<ans;
   return 0;
 }

P4011 孤岛营救问题

题意：钥匙-锁模型迷宫，点上有钥匙，边上有锁，一个师傅走迷宫，经过一个有钥匙的点可以把钥匙撇到皮带上面，边上有锁，锁对应钥匙。皮带可以撇一大串钥匙。问最短时间。点数 100，钥匙颜色数 14。

做法：由于钥匙不太富，所以设个状态 dp_{u,S} 表示走到 u，皮带上撇起 S 里面的一大串钥匙的答案。然后直接坐板凳就可以了得咩。

LOJ2999 [JOISC2015] 钥匙 && P4890 Never·island 未来岛的开锁问题

题意：

有 n 个师傅从 0 到 M 时刻上班，第 i 个师傅会在 S_i 时刻去饮水机洗手再在 T_i 时刻回来。没撇钥匙的师傅出门以后不能关门，撇起钥匙的师傅可以随便进出，没撇钥匙的师傅要门开起才能回去，撇起钥匙的师傅回去的时候可以把门锁起。总共 K 串钥匙分给这些师傅，求分配方案使得关门时间最小。

做法：

考虑每个时间段的贡献。如果前一个时间点是某个师傅出去洗手，后面一个时间点也是某个师傅出去洗手，那么这段时间可以关起当且仅当前面一个师傅撇起钥匙。如果前面一个时间点是某个师傅回来，后面一个时间点也是某个师傅回来，那么这段时间可以关起当且仅当后面的师傅撇起钥匙。如果前面一个的时间点是某个师傅回来，后面一个时间点是某个师傅出去洗手，那么不管有没有师傅去洗手这段时间一定能关起。如果前面一个时间点是某个师傅出去洗手，后面一个时间点是某个师傅回来，此时如果它们是同一个师傅，那么只要这个师傅撇起钥匙这段时间就可以关起，不然必须两个师傅都撇起钥匙才能关起。我们把必须两个师傅同时撇起钥匙的时间段嗲出来连条边，可以发现这张图就是一大串一大串的链，跟撇钥匙一样滴把串串些撇到一起在序列上做个 DP 算一下贡献就可以了得咩。具体来说就是 dp_{i,j,0/1} 表示链上前 i 个师傅撇起 j 串钥匙，师傅 i 撇没撇钥匙，转移就枚举一下前一个师傅有没有撇钥匙转移过来，撇起钥匙的话就加上这个师傅撇钥匙的贡献，要是两个师傅都撇起钥匙就加上这部分的贡献就可以了得咩。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,k,tot,b[2008],c[2008],dp[2][2008][2],nxt[2008];
struct node
 {
  int x,id,typ;
 bool operator<(node q){return x<q.x;
}
}a[6666];
void cmax(int&x,int y){if(y>x)x=y;
}
int main()
{scanf("%d%d%d",&n,&m,&k);
for(int i=1,x;i<=n;++i)
  {
 scanf("%d",&x);a[++tot]=(node){x,i,0};
scanf("%d",&x),a[++tot]=node{x,i,1};
 }
 sort(a+1,a+tot+1);
int yu=m+a[1].x-a[tot].x;
  for(int i=1;i<tot;++i)
   {
 int len=a[i+1].x-a[i].x;
 if(a[i].typ&&!a[i+1].typ)
 yu+=len;
 else if(a[i].typ&&a[i+1].typ)c[a[i+1].id]+=len;
else if(!a[i].typ&&!a[i+1].typ)
c[a[i].id]+=len;
  else if(a[i].id==a[i+1].id)
c[a[i].id]+=len;
else nxt[a[i+1].id]=a[i].id,b[a[i].id]+=len;
  }
for(int i=1,las=0;i<=n;++i)
 if(!b[i]){
 nxt[las]=i;
  while(nxt[las])
las=nxt[las];
}
dp[0][0][0]=yu;
 int w=0;
  for(int i=nxt[0];i;i=nxt[i]){
w^=1;
for(int j=0;j<=k;++j)for(int t:{0,1})
  {if(!dp[!w][j][t])
continue;
cmax(dp[w][j][0],dp[!w][j][t]);
   cmax(dp[w][j+1][1],dp[!w][j][t]+t*b[i]+c[i]);
 dp[!w][j][t]=0;
  }
}
cout<<max(dp[w][k][0],dp[w][k][1]);
 return 0;
  }

P4436 [HNOI/AHOI2018]开锁游戏

题目描述：

一个链上的钥匙-锁模型。一个数轴上一些边可能有锁，给出这些锁对应的钥匙的位置。有 q 个师傅要在迷宫上开车，给一个起点的位置 s，给一个北京的位置 t，现在师傅要开车去北京，每次可以随便往哪个方向走，每遇到一串钥匙就可以撇到皮带上面，可以通过一个边当且仅当师傅现在的皮带上拥有其对应的钥匙。给每个师傅求出他能不能走得到北京？

思路：

我们考虑进行一个板凳的坐。这个题本质上就是一个记忆化搜索哈，搜索就是坐板凳。我们考虑先把连续一段没有锁的板凳给锁到一起，然后从每个点开始搜索。注意到每个点能到的点是一个区间，我们每次搜索就考虑当前区间能不能向左向右扩展，看一下我们现在的区间是否包含扩展出去的锁的钥匙，写一个记忆化搜索来坐板凳就可以了得咩。

参考代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,p,pos[1000010],zuo[1000010],you[1000010],wei[1000010],xia[1000010];
void dfs(int x)
 {
  if(zuo[x]&&you[x])return;
  zuo[x]=x,you[x]=xia[x];
   while (1){
  bool kue=0;
    if(zuo[x]> 1&&wei[pos[zuo[x]-1]]>=zuo[x]&&wei[pos[zuo[x]-1]]<=you[x])
      {
    kue=1;
    dfs(wei[zuo[x]-1]);
    zuo[x]=zuo[wei[zuo[x]- 1]];
  }
  if(you[x]<n&&wei[pos[you[x]]]>=zuo[x]&&wei[pos[you[x]]]<=you[x])
   {
    kue=1;
    dfs(wei[you[x] + 1]);
    you[x]=you[wei[you[x] +1]];
  } if (!kue) break;}}
int main()
 {
   scanf("%d%d%d",& n, &m ,&p );
  while(m--){int x,y;
 scanf("%d%d",&x,&y);pos[x]=y;
}
  for(int i=1;i<=n;++i)
 if(i==1||pos[i-1])
  wei[i]=xia[i]=i;
    else
   xia[wei[i]=wei[i -1]]= i;
   for(int i=1;i<=n;++i)
  if(wei[i]==i)
    dfs(i);
    while(p--){
   int S,T;
  scanf("%d%d",&S,&T);
    S=wei[S];
    if (T>=zuo[S]&&T<=you[S])
   printf("YES\n");
     else   printf("NO\n");
   }
return 0;
 }

LOJ2397 [JOISC 2017 Day 3] 幽深府邸

跟上面那道题差不多得咩，区别是同一个颜色有好几把锁，每个点上的钥匙也是一串一串滴，就还是一个坐板凳的问题，每个锁找到它左边和右边的钥匙的位置，每次暴力去坐板凳来扩展这个开锁区间就可以了得咩，666666

#include <bits/stdc++.h>
using namespace std;
int n,q,c[666666],t[666666],a[666666],p[666666],r[666666],l[666666],zuo[666666],you[666666];
 void seat(int x){if(zuo[x]&&you[x])return;
zuo[x]=you[x]=x;while(1){
  bool t=0;
   if(r[zuo[x]-1]&&r[zuo[x]-1]<=you[x])
  {seat(zuo[x]-1);
    if(zuo[zuo[x]-1]<zuo[x])t=1,zuo[x]=zuo[zuo[x]-1];
     if(you[zuo[x]-1]>you[x])t=1,you[x]=you[zuo[x]-1];
   }if(l[you[x]+1]&&l[you[x]+1]>=zuo[x]){seat(you[x]+1);
    if(zuo[you[x]+1]<zuo[x]) t=1,zuo[x]=zuo[you[x]+1];
    if(you[you[x]+1]>you[x])t=1,you[x]=you[you[x]+1];
   }if(!t)
break;}
 }
int main()
 {scanf("%d",&n);
for(int i=1;i<n;i++)scanf("%d",&c[i]);
 for(int j=1;j<=n;j++)
  {scanf("%d",&t[j]);t[j]+=t[j-1];
 for(int k=t[j-1]+1;k<=t[j];k++)  scanf("%d",&a[k]);
  }for(int i=n;i>1;i--)
 {for(int j=t[i-1]+1;j<=t[i];j++)p[a[j]]=i;
 r[i-1]=p[c[i-1]];
 }memset(p,0,sizeof p);
 for(int i=1;i<n;i++)
 {for(int j=t[i-1]+1;j<=t[i];j++)p[a[j]]=i;
  l[i+1]=p[c[i]];
 }for(int i=1;i<=n;i++)
 {seat(i);}scanf("%d",&q);
   while(q--)
 {int x,y;scanf("%d%d",&x,&y);
   if(y>=zuo[x]&&y<=you[x])printf("YES\n");
   else   puts("NO");
 }
  return 0;
 }

P8339 [AHOI2022] 钥匙

这个安徽的师傅些出的题那是相当的规范！非常珍贵的既有思维难度又有代码难度的高质量好题！

题意

一个相当经典的钥匙-锁模型：给定一个树形结构的迷宫，每个节点上有一串钥匙或者一个锁。钥匙和锁有颜色，一种颜色的钥匙开一种颜色的锁。有 Q 个师傅，第 i 个师傅要开车沿最短路从 s_i 到 t_i，遇到一串钥匙就可以把它撇在皮带上面，遇到一个锁就可以拿皮带上撇起的对应颜色的钥匙来开锁，然后这个钥匙会被挂烂。问你最多能开好多个锁。保证同种颜色的钥匙最多只有 5 串。

题解

每种颜色的贡献是独立的，那么对每种有颜色我们把这些钥匙和锁嗲出来建一棵虚树。利用每种钥匙的钥匙不超过 5 串的条件，我们枚举钥匙 yo 和锁 so，看看哪些会对哪些路径产生贡献（即获得 yo 并使用它来开 so）？可以发现充要就是从 yo 到 so 的简单路径上任何一个前缀钥匙都比锁多（除了 so），且钥匙和锁一样多。从每个 yo 开始 DFS 找到所有合法的数对 (yo,so)。这些可以贡献到所有包含 (yo,so) 的路径上。转到 DFS 序上做二维数点，分三种情况，一种是 yo 是 so 的祖先，一种是 so 是 yo 的祖先，或者没有祖孙关系。就是个二维加矩形加单点查，离线下来用树状数组做就可以了得咩。

代码：

#include <bits/stdc++.h>
using namespace std;
int cnt,en,fa[1000010][20],dfn[1000010],tim=0,ord[1000010<<1],te=0,dep[1000010],n,siz[1000010],col[1000010],key[1000010],m,vis[1000010],inq[1000010],stk[1000010],top,ans[2000010],tree[1000010];
struct edge{int head,to,nxt;}ed[2000010];
void addedge(int from,int to)
 {
  ed[++en].to=to;ed[en].nxt=ed[from].head;ed[from].head=en;}
  void dfs(int now,int f){
      dfn[now]=++tim;ord[now]=++te;fa[now][0]=f;dep[now]=dep[f]+1;siz[now]=1;
   for(int i=1;i<20;i++)fa[now][i]=fa[fa[now][i-1]][i-1];
       for(int i=ed[now].head;i;i=ed[i].nxt){
           int v=ed[i].to;
    if(v==f)continue;dfs(v,now);siz[now]+=siz[v];}
   ord[now+n]=++te;}
  int LCA(int a,int b)
 {
int u=a,v=b;if(dep[u]<dep[v])
swap(u,v);int k=dep[u]-dep[v];
for(int i=0;i<20;i++)if((k>>i)&1)u=fa[u][i];if(u==v)return u;
  for(int i=19;~i;--i)if(fa[u][i]!=fa[v][i])
      {u=fa[u][i],v=fa[v][i];}return fa[u][0];}
  int zu(int x,int k){
      for(int i=0;i<20;i++)if((k>>i)&1)x=fa[x][i];return x;}
 vector<int>nxt[1000010],C[1000010],b;
void dfs1(int now,int fa,int c,int cnt){
if(col[now]==c&&key[now])cnt++;
 if(col[now]==c&&!key[now])
     {
  --cnt;
   if(!cnt){b.push_back(now);return;}}
    for(int i:nxt[now])
   {if(i==fa)continue;dfs1(i,now,c,cnt);}return;
 }
  struct ADD
 {int x,l,r;ADD()
 {}
  ADD(int X,int L,int R):x(X),l(L),r(R){

  }bool operator<(const ADD&b)
 const{return abs(x)<abs(b.x);}
  bool operator>(const ADD&b)const
  {
 return abs(x)>abs(b.x);}}add[20000010];
struct Query{int id,x,y;}q[2000010];
 bool cmp(Query a,Query b)
 {return a.x<b.x;}
  bool cmp2(int a,int b){return dfn[a]<dfn[b];}
bool cmp3(int a,int b){return ord[a]<ord[b];
}
void calc(int c){
 vector<int>S=C[c];
  if(S.size()==1)return;
 sort(S.begin(),S.end(),cmp2);
 int p=S.size(),r=1;
 for(int i=0;i<p;i++)vis[S[i]]=inq[S[i]]=1,S.push_back(S[i]+n);
for(int i=1;i<p;i++)
 {int q=LCA(S[i],S[i-1]);if(vis[q])continue;
vis[q]=1;S.push_back(q);S.push_back(n+q);}
 if(!vis[1])vis[1]=1,S.push_back(1),S.push_back(1+n);
   sort(S.begin(),S.end(),cmp3);
 p=S.size();
  top=0;
 for(int i=0;i<p;i++){
     if(S[i]<=n) stk[++top]=S[i];
     else
       {int x=stk[top--];
  int y=stk[top];
   if(y){nxt[y].push_back(x);nxt[x].push_back(y);r=y;}}
}
  for(int i:S)
       {if(i>n)
      continue;
   if(col[i]==c&&key[i]){
       b.clear();dfs1(i,0,c,0);
     for(int j:b)
          {
              int x=i,y=j,lca=LCA(i,j);
     if(lca==x)
    {
     int q=zu(y,dep[y]-dep[x]-1);
      if(dfn[q]!=1){
          add[++cnt]=ADD(1,dfn[y],dfn[y]+siz[y]-1);
           add[++cnt]=ADD(-dfn[q],dfn[y],dfn[y]+siz[y]-1);}
      if(dfn[q]+siz[q]-1!=n)
          add[++cnt]=ADD(dfn[q]+siz[q],dfn[y],dfn[y]+siz[y]-1);}
        else if(lca==y){int q=zu(x,dep[x]-dep[y]-1);
        if(dfn[q]!=1)
      {add[++cnt]=ADD(dfn[x],1,dfn[q]-1);
  if(dfn[x]+siz[x]-1!=n)add[++cnt]=ADD(-(dfn[x]+siz[x]),1,dfn[q]-1);
}
   if(dfn[q]+siz[q]-1!=n){
         add[++cnt]=ADD(dfn[x],dfn[q]+siz[q],n);
       if(dfn[x]+siz[x]-1!=n)
           add[++cnt]=ADD(-(dfn[x]+siz[x]),dfn[q]+siz[q],n);}}
        else
       {add[++cnt]=ADD(dfn[x],dfn[y],dfn[y]+siz[y]-1);
   if(dfn[x]+siz[x]-1!=n)add[++cnt]=ADD(-(dfn[x]+siz[x]),dfn[y],dfn[y]+siz[y]-1);}
  }
   }
}
   for(int i=0;i<p;i++)
  {int x=S[i];
 if(x>n)x-=n;vis[x]=inq[x]=0;nxt[x].clear();}
}
void Add(int x,int y)
{
    for(int i=x;i<=n;i+=i&-i)tree[i]+=y;}
 int sum(int x)
{int res=0;for(int i=x;i;i-=i&-i)res+=tree[i];
return res;}
int main()
 {
     scanf("%d%d",&n,&m);
 for(int i=1,t;i<=n;i++){
     scanf("%d%d",&t,&col[i]);
      if(t==1)key[i]=1;else key[i]=0;
 C[col[i]].push_back(i);}
 for(int i=1,u,v;i<n;i++)
     {
     scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);}dfs(1,0);
 for(int i=1;i<=n;i++)
     if(C[i].size())calc(i);
 for(int i=1;i<=m;i++)
{int x,y;
 scanf("%d%d",&x,&y);q[i].x=dfn[x];q[i].y=dfn[y];q[i].id=i;
}
  sort(q+1,q+m+1,cmp);sort(add+1,add+cnt+1);
 int t=1;for(int i=1;i<=cnt;i++){
     int x=add[i].x,y=1;if(abs(x)!=abs(add[i-1].x))
  {while(t<=m&&q[t].x<abs(x))ans[q[t].id]=sum(q[t].y),++t;}
   if(x<0)y=-1,x=-x;Add(add[i].l,y);
 if(add[i].r!=n)Add(add[i].r+1,-y);}while(t<=m)ans[q[t].id]=sum(q[t].y),
 ++t;
   for(int i=1;i<=m;i++)
  printf("%d\n",ans[i]);
 return 0;
}

P8519 [IOI2021] 钥匙

闲话

这个 IOI 的题啊出的是相当的不规范，弄个这个交互题的格式，麻烦得很。建议这个 IOI 比赛的出题人整成从文件里面读数据！哪有这样子交题连个 main 函数都没得的咩？现在外国的这些小伙子些净整些洋歪歪的，简直把我整腾了！

题意

一个经典的钥匙-锁模型。有一个 n 个点 m 条双向边的迷宫。每条边上有某种颜色的锁，每个点上有某种颜色的钥匙。一种颜色的钥匙开一种颜色的锁。如果一个师傅从点 i 开始在迷宫里头转圈圈，进到一个房子就把钥匙串起撇到皮带上面，皮带上要有对应颜色的钥匙才能开锁走过一条边，设师傅以 i 为起点开始能转到的点数是 p_i，要求出 p_i 最小的那些 i 的集合。

题解

我们可以发现，因为是要找 p_i 最少的那些，所以如果 x 能转到 y，y 可以转到的点 x 肯定也可以先转到 y 再转到，那么 p_y 肯定不得超过 p_x 三，如果反过来 y 转不到 x 那 x 肯定没用了，此时 p_x 肯定严格比 p_y 大。那把这个每个点能到的拿个并查集缩一下。对每个并查集里面的集合，我们从这个根节点，也就是被所有点能到达的这个点开始 BFS 坐板凳，找到能到达的另一个集合合并起来。这个过程是啥子复杂度的捏？其实跟 Boruvka 算法的思想是差不多的。因为我们每次会找到一个集合跟他合并，那集合的数量每次砍半，因此这个过程只需要进行 \mathcal O(\log n) 轮。每轮我们坐板凳的复杂度是 \mathcal O(n) 的，因此总复杂度就是一个 \mathcal O(n\log n) 了得咩。

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
vector<pair<int,int>>e[300010];
vector<int>res,ans,col[300010],pw,t;
int n,m,R[300010],vis[300010],in[300010],q[300010],mn=1e9,fin[300010],f[300010];
int find(int x)
{return x==f[x]?x:f[x]=find(f[x]);
}
void bfs(int s){
 bool flag=1;
  queue<int>q;
q.push(s);
t.push_back(s);
 while(!q.empty())
  {
  int x=q.front();
   q.pop();
   if(find(x)!=s){
 flag=0;
  f[s]=find(x);
 vis[find(x)]=1;
  break;}
    if(vis[x])continue;
 vis[x]=1;
  ans.push_back(x);
  if(!in[R[x]])
{
 in[R[x]]=1;
  for(int i:col[R[x]])
  q.push(i),t.push_back(i);}
 for(pair<int,int>i:e[x])
  {
   int v=i.first,w=i.second;
 if(in[w])
  q.push(v),t.push_back(v);else
   col[w].push_back(v),pw.push_back(w);
   }
    }
 if(flag)
   {fin[s]=1;
 if(ans.size()<mn)
  {
  mn=ans.size();
    res=ans;}
else if(ans.size()==mn)for(int i:ans)res.push_back(i);
}for(int i:pw)
 col[i].clear();
   for(int i:t){
  in[R[i]]=0;}
 pw.clear();
 t.clear();
  ans.clear();}
  vector<int>find_reachable(vector<int>r,vector<int>u,vector<int>v,vector<int>c)
{n=r.size(),m=u.size();
 for(int i=1;i<=n;++i)
   R[i]=r[i-1]+1,f[i]=i;
for(int i=0,x,y,w;i<m;++i)
 {x=u[i]+1,y=v[i]+1,w=c[i]+1;
 e[x].push_back(mp(y,w));
  e[y].push_back(mp(x,w));
}
  while(1)
   {
 bool flag=1;for(int i=1;i<=n;++i)vis[i]=0;
  for(int i=1;i<=n;++i)
 if(find(i)==i&&!fin[i]&&!vis[i])
  bfs(i),flag=0;
if(flag)break;}
 vector<int>mea(n);
for(int i:res)  mea[i-1]=1;
  return mea;
   }

CF1519F 胸和钥匙

cf edu 的题，果然是相当的规范！我很喜欢哈！好题难得！大家一定要珍惜哈！

还是一个钥匙-锁模型哈！题目就是说有一些胸和一些钥匙，你要花钱给每个胸上上几把锁锁起，让另一个师傅来开锁。另一个师傅买钥匙是要花点钱哈！买到了钥匙就能随便开相应的锁。把胸上所有锁都开开以后他可以拿到胸里头的钱哈。那就问你要怎么花最少的钱上锁才能让这个师傅挣不到钱喃？

我们先来看一下这个师傅是啷们做起得。我们把钥匙和胸连出来一个二分图咩！他要用左边的钥匙去开右边的锁，我们要让他赚不到钱，就是找不出来一个找钥匙的方案让它在胸里面挣到的钱减去钥匙的钱超过零。这个是不是有点像我们滴这个洞洞（Hall）定理咩？你看哈，这个钱的问题有点恼火，那我把这个图拗一下，每个点上是好多钱我就给他拆出来几个点，左右都是这样的哈，该连的边还是都给他连起！那我们可以发现哈，这个挣不到钱的条件就相当于右边找得到一个完美匹配了得咩。没学过洞洞定理和二分图匹配的同学可以下来找我给你讲一下咩！其实二分图匹配还是很简单滴哈，就是一个坐板凳的问题得咩。

那我们啷们算答案喃？我们枚举当前的胸上匹配了左边哪些点，花费就是要加那些至少用了一次的那些哈。那到这里我们发现就这里就是一个坐板凳滴问题了得咩！坐板凳的话我们首先就是要搞清楚哪边是人哪边是板凳哈。我们的目标是让胸都能匹配到起一个钥匙，那么就把胸当人，钥匙就是板凳，搜到右边的某个胸的时候，就去安排它去坐哪些板凳。我们写搜索就是要先写个能跑滴，再写个能过滴哈。你发现你的代码时间成本比较高，出题人糙了个数据把你嘿嗑到起了，那就需要剪枝了哈。那这个题我们需要啷们剪枝喃？首先我们可以剪去不用的状态哈，也就是说其实我们只用关心每个钥匙用了好多个，只把这个个数记下来就可以了！然后我们就可以设计一个记忆化了得咩！我们把板凳编码成一个数，然后记录到一个数组后头，这下是不是就可以重复利用答案了咩！编码解码也是搜索中很重要的技巧哈！然后还有一个剪枝是记录一下每个胸拆出来的点里头还剩到起好多个点没有匹配哈，每次匹配的时候都不能超过这个界，那么我们就在搜索的过程中就能保证每个胸没用多了哈。另外一个剪枝是如果我们搜到一个本来就是无解的状态，我们就直接跳过不搜了就可以了得咩。像这样子剪了枝过后，你就可以发现我们的程序跑得风快哈，一哈就直接过了哈！

代码放到这里了咩！大家自己咩一咩咩！

#include <bits/stdc++.h>
using namespace std;
int n,m,a[8],b[8],c[8][8],s[8],f[8][66666];
 void sit(int u,int t,int seat,int g,int x,int y)
  {if(u>m){
    if(t==a[x]){f[x][seat]=min(f[x][seat],f[x-1][y]+g);
 }
 return;}
 if(f[x-1][y]!=0x3f3f3f3f)
{
  for(int i=0;i<=100;i++)
  {if(t+i>a[x])break;
 if(i+y/s[u-1]%(b[u]+1)>b[u])
  {break ;}
  int q;
   if(i)q=c[x][u];
 else q=0;
 sit(u+1,t+i,seat+i*s[u-1],g+q,x,y);
}}
  }
int main()
 {
  scanf("%d%d",&n,&m);
 for(int i=1;i<=n;i++)scanf("%d",&a[i]);
 for(int i=1;i<=m;i++) scanf("%d",&b[i]);
  for(int i=1;i<=n;i++)
  {for(int j=1;j<=m;j++)scanf("%d",&c[i][j]);
  }
 s[0]=1;
 for(int i=1;i<7;i++)s[i]=s[i-1]*(b[i]+1);
  memset(f,0x3f,sizeof f);
f[0][0]=0;
 for(int i=1;i<=n;i++)
for(int j=0;j<s[m];j++)
  {
 sit(1,0,j,0,i,j);
   }
int an=0x3f3f3f3f;
 for(int i=0;i<s[m];i++)an=min(an,f[n][i]);
   if(an==0x3f3f3f3f)
 {cout<<"-1";}
 else{cout<<an;}
  return 0;
  }