“蔚来杯“2022牛客暑期多校训练营10 F.Shannon Switching Game?

原题链接

传送

题目大意

香浓切换游戏的变体规则如下：
给定有重边的无向图 $G=(V,E)$， 和两个点 $s,t\in V$。 最初在 $s$ 点上有一个令牌。两个玩家 $JoinPlayer$ 和 $CutPlayer$ 轮流进行以下操作，Cut Player先手：

• 如果轮到Join Player，如果令牌在点 $u$ ，则选择边 $(u,v)\in E$，删除它并将令牌移动到点 $v$。
• 如果轮到Cut Player，如果令牌在点 $u$ ，则选择边 $(u,v)\in E$，删除它。
  当任意玩家无法进行操作时，游戏结束。
  如果令牌在游戏期间到达点 $t$ ，则Join Player获胜。反之Cut Player获胜。
  假设双方均采取最优策略，给定图 $G$ ，求谁回获胜。

题解

考虑，若当前只有一条路可以走向终点，那么Cut Player 就可以删去这一条路获得胜利。
而当前选择 $>1$ 可以走向终点时，Cut Player只能删去一条，还可以继续走。
那么答案就很明晰了，选择一条路，若其中的每一个节点都有超过一种方案能到达终点，则Join Player获胜，反之Cut Player获胜。
由于在图上进行操作，我们考虑倒着枚举，从终点开始遍历，如果从终点可以到达一个节点两次即以上则它可以继续向前，表明该点是可以到达终点的，如果能到达起点，则存在上面说明的路径。
注意：终点不可以通过多次，否则会死循环。

参考代码

#include
using namespace std;
const int N=105;
vector<int> v[N];
int b[N];
int n,m,s,t,T;
void dfs(int x)
{
	b[x]++;
	if(b[x]!=2)     //若小于2，则无法通过，若大于2，则已经通过
		return;
	for(int i=0;i<v[x].size();i++)
		dfs(v[x][i]);
}
int main()
{
//	freopen("1.txt","r",stdin);
//	freopen("2.txt","w",stdout);
    cin>>T;
    while(T--)
    {
        scanf("%d%d%d%d",&n,&m,&s,&t);
        for(int i=1;i<=n;i++)
        	v[i].clear(),b[i]=0;
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            v[x].push_back(y);
            v[y].push_back(x);
        }
        b[t]=1;          //终点不允许通过多次
        dfs(t);
//        for(int i=1;i<=n;i++)
//        	cout<
        if(b[s]>=2)          //存在路径
            puts("Join Player");
        else   
            puts("Cut Player");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41