[NERC2018] Cactus Search 题解

FFTotoro · 2024-11-14 21:53:41 · 题解

考虑每次选择一个点，使得不管回答哪一个结点，最终可能成为答案的点集最小化。

有结论：每次选出符合上面条件的一个点，必然可以使得最终点集的大小除以 2（证明可以考虑，假设询问 u，v 为返回的结点，且有大于一半的点可以成为答案，即有一半的可以成为答案的点到 u 的路径上经过了 v，那么询问 v 更优）。于是询问次数不超过 \lceil\log_2n\rceil，可以通过。

找单个结点的时间复杂度为 O(n^2)，由于要找 n 次所以时间复杂度为 O(n^3)。

放代码：

#include<bits/stdc++.h>
using namespace std;
const int I=1e9;
int main(){
  ios::sync_with_stdio(false);
  int n,m; cin>>n>>m;
  vector f(n,vector<int>(n,I));
  for(int i=0;i<n;i++)
    f[i][i]=0;
  for(int i=0;i<m;i++){
    int s; cin>>s;
    vector<int> v(s);
    for(auto &i:v)cin>>i,i--;
    for(int i=1;i<s;i++)
      f[v[i-1]][v[i]]=f[v[i]][v[i-1]]=1;
  }
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      for(int k=0;k<n;k++)
        f[j][k]=min(f[j][k],f[j][i]+f[i][k]);
  for(int r=0;r<n;r++){
    vector<bool> b(n,true);
    while(1){
      int v=n+1,u=-1;
      for(int i=0;i<n;i++)
        if(b[i]){
          int s=0;
          for(int j=0;j<n;j++)
            if(b[j]&&f[i][j]==1){
              int c=0;
              for(int k=0;k<n;k++)
                c+=b[k]&&f[j][k]<f[i][k];
              s=max(s,c);
            }
          if(s<v)v=s,u=i;
        }
      cout<<u+1<<endl;
      string s; cin>>s;
      if(s=="FOUND")break;
      int x; cin>>x,x--;
      for(int i=0;i<n;i++)
        if(f[x][i]>=f[u][i])b[i]=false;
    }
  }
  return 0;
}