[EGOI2022] Social Engineering 题解

FFTotoro · 2025-01-23 19:54:03 · 题解

尝试猜测 Maria 会赢的充分条件：令在原图中与结点 1 相邻的点为“关键点”，假设将结点 1 和与其相邻的所有点的边都删去，只需要存在一个连通块中包含奇数个关键点，这个时候 Maria 每次随便选一个还没选过的点挑战就能赢。

对于其他情况，可以证明我们一定能赢，所以上述条件是充要的。只需要将每个连通块内的关键点两两匹配，并对于每一对匹配的关键点 (u_i,v_i) 都找出一条 u_i 到 v_i 的简单路径 p_i，使得对于任意两条不同的路径 p_i,p_j，都不存在一条边同时出现在它们之中。

当 Maria 问到一个关键点时（不妨设为 u_i），只需沿着 p_i 一路挑战到 v_i，最后挑战结点 1。

考虑每个连通块，求出满足条件的匹配。求出该连通块的一棵生成树，在树上自底而上贪心匹配（能匹配就匹配）；由于连通块内关键点个数为偶数，这样匹配是满足条件的。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int GetMove();
void MakeMove(int v);
bool Check(vector<vector<int> > g){
  int n=g.size();
  vector<bool> w(n),b(n);
  for(int i:g[0])w[i]=true;
  // w[i] 表示点 i 是否是关键点
  for(int i=1;i<n;i++)
    if(!b[i]){
      int c=0;
      function<void(int)> dfs=[&](int u){
        c+=w[u];
        for(int i:g[u])
          if(i&&!b[i])b[i]=true,dfs(i);
      };
      if(b[i]=true,dfs(i);c&1)return false;
    }
  return true;
} // 判断是否能赢
void SocialEngineering(int n,int m,vector<pii> e){
  vector<vector<int> > g(n);
  for(auto &[u,v]:e){
    g[--u].emplace_back(--v);
    g[v].emplace_back(u);
  }
  if(!Check(g))return;
  vector<int> id(n,-1);
  vector<vector<int> > pn(n),p;
  // pn[i] 存储了从 i 开始的路径
  // p[i] 存储了最终匹配中的第 i 条路径
  vector<bool> w(n),b(n);
  for(int i:g[0])w[i]=true;
  for(int i=1;i<n;i++)
    if(!b[i]){
      function<int(int)> dfs=[&](int u){
        vector<int> q;
        for(int i:g[u])
          if(i&&!b[i]){
            b[i]=true;
            if(int v=dfs(i);v)
              q.emplace_back(v);
          }
        if(w[u])q.emplace_back(u);
        while(q.size()>1){
          int x=q.back(); q.pop_back();
          int y=q.back(); q.pop_back();
          auto t=pn[x]; t.emplace_back(u);
          t.insert(t.end(),pn[y].rbegin(),pn[y].rend());
          id[x]=id[y]=p.size(),p.emplace_back(t);
        } // 进行匹配
        if(!q.empty())pn[q[0]].emplace_back(u);
        return q.empty()?0:q[0];
      };
      b[i]=true,dfs(i);
    }
  while(1){
    int x=GetMove();
    if(--x<0)break;
    if(x==p[id[x]].back())
      reverse(p[id[x]].begin(),p[id[x]].end());
    for(int i:p[id[x]])
      if(i!=x)MakeMove(i+1);
    MakeMove(1);
  } // 模拟过程
}