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

原题题面：https://ac.nowcoder.com/acm/contest/33195/F

题目大意：

给定可能有重边的无向图$G=(V,E)G=(V,E)$,和两个点$s,t\in Vs,t\backslash in\; V$，最初在s点有一个令牌，两个玩家Join Player.Cut Player轮流执行以下操作，Cut Player先手.

:如果轮到Join Player,假如令牌在点$uu$,则选择边$(u,v)\in E(u,v)\backslash in\; E$,删除它并将令牌移动到$vv$.

:如果轮到Cut Player,假如令牌在点$uu$,则选择边$(u,v)\in E(u,v)\backslash in\; E$,删除它.

当任意玩家无法操作时，游戏结束

如果在游戏期间令牌到达了$tt$,则Join Player获胜，反之Cut Player获胜

两人均采用最佳策略，问谁会获胜

分析：

不妨将题目倒过来考虑，以$tt$为起点，设能到达的点$ii$的$go[i]=1go[i]=1$,反之$go[i]=0go[i]=0$,最后判断$go[s]go[s]$是否为1即可

思路有了，再来考虑如何判断一个点是否能到达，因为Cut Player先手，如图（见下），从点t开始，可以发现只有点$jj$可以到达，但点$i,si,s$却不可，因为Cut Player可以抢先删除$ss$与$ii$之间的路径，让Join Player无路可走

结论:

对于每一个点$uu$，若存在有两条$(u,v)(u,v)$(即有重边)且$go[v]=1go[v]=1$,则$go[u]=1go[u]=1$,反之$go[u]=0go[u]=0$

即从点$tt$跑一次bfs即可

代码：

 #include<bits/stdc++.h>
using namespace std;

const int MXN=10007;
int n,m,s,t;
int g[110][110];
int go[107];
int vis[107];
void bfs(int start){
	int now,edge;
	vis[start]=1;
	queue<int> q;
	q.push(start);
	while(!q.empty()){
		edge=0;
		now=q.front(); q.pop();
		for(int i=1;i<=n;i++){
			if(g[now][i]){
				go[i]+=g[now][i];
				if(!vis[i]&&go[i]>1){
					q.push(i);
					vis[i]=1;
				}
			}
		}
	}
}
int main(){
	int T,u,v;
	scanf("%d",&T);
	while(T--){
		memset(g,0,sizeof(g));
		memset(vis,0,sizeof(vis));
		memset(go,0,sizeof(go));
		scanf("%d%d%d%d",&n,&m,&s,&t);
		for(int i=1;i<=m;i++){
			scanf("%d%d",&u,&v);
			g[u][v]++;
			g[v][u]++;
		}
		bfs(t);
		if(go[s]<=1) printf("Cut Player\n");
		else printf("Join Player\n");
	}
}