自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 22:51:53，当前版本为作者最后更新于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;
}