2022牛客多校（十）

2022牛客多校（十） 一、比赛小结

比赛链接："蔚来杯"2022牛客暑期多校训练营10

二、题目分析及解法（基础题） F、Shannon Switching Game?

题目链接：F-Shannon Switching Game?

题意：

给定一个无向图，初始时有一个token在s点，两个玩家Join Player和Cut Player轮流行动，Cut Player先动。Cut Player每次可以移除一条和token所在位置相邻的边, Join Player每次可以将token沿着一条未删除边移动, 如果token在某刻被移动到t则Join Player获胜，否则Cut Player获胜，求双方最优策略下的胜者。

题解：

• 我们可以求出在双方最优策略下使得Join Player可以将token移动到t的所有token起点集合,把这个集合叫做good set

• 首先,t点一定是在good set中的，我们从t开始逐步构建good set。某个不在good set中的顶点v如果有至少两条边连向good set中的某个顶点，那么从该点出发的话，由于Cut Player在一次操作中只能切断其中的一条边，那么Join Player一定可以在一次操作后将token移动到good set中的某个顶点，因此此时v也在good set中。

• 如果在某一时刻，任何不在good set中的顶点都只有至多一条边连向good set中的某个顶点,那么从不在good set中的任一顶点出发，Cut Player只需要每次切断可能连向good set的边即可,那么此时不在goodset中的顶点一定都不能到达t点。

• 构建可以通过维护一个队列来实现，时间复杂度为O(n+m),其中n是顶点个数,m是边数 。

代码：

#include 
using namespace std;
int T, n, m, s, t;
const int maxn = 1e2 + 5;
int g[maxn][maxn], num[maxn];
bool vis[maxn];
bool bfs() {
  queue q;
  q.push(t);
  vis[t] = 1;
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = 1; i  1) {
        q.push(i);
        vis[i] = 1;
      }
    }
  }
  return num[s] > 1;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> T;
  while (T--) {
    memset(vis, 0, sizeof vis);
    memset(g, 0, sizeof g);
    memset(num, 0, sizeof num);
    cin >> n >> m >> s >> t;
    while (m--) {
      int u, v;
      cin >> u >> v;
      g[u][v]++;
      g[v][u]++;
    }
    cout  x;
  cin >> B;
  for (int i = 1; i > x;
  a = ceil(1.0 * A / 10), b = ceil(1.0 * B / 10);
  for (int i = b; i