HDU 3267 Graph Game（博弈论+图论+暴力）

题面传送门

题意：

有一棵 \(n\) 个节点的图 \(G\)，R 和 B 两个人轮流操作，R 先操作。

每次操作 R 可以染红任意一条未染色的边，B 可以染蓝任意一条未染色的边

R 的目标是染成一棵全蓝的生成树，R 的目标是阻止后手染成一棵全蓝的生成树，问谁会赢。

\(n \in [1,10]\)，\(m \in [1,30]\)

yet another 博弈论 problem......

不难猜出本题的结论是如果 \(G\) 中存在两棵边集不相交的生成树，答案为 \(\texttt{YES}\)，否则答案为 \(\texttt{NO}\)，你手玩几组数据应该就可以看出来。

但是怎么证明呢？

对于游戏中任意一个局面，我们分以下几种情况考虑：

如果 \(G\) 中存在两棵生成树 \(T_1,T_2\)，满足 \(T_1,T_2\) 只由蓝边或无色边组成，并且 \(T_1,T_2\) 中无色边组成的边集不相交。

如果 R 染红的边不在 \(T_1,T_2\) 中，那么 B 随便染蓝一条边都可以保持这个局面。因为你染蓝这条边后 \(T_1,T_2\) 依然满足上述条件。

如果 R 染红的边在 \(T_1,T_2\) 中，不妨假设 R 染红的边为 \(e_1 \in T_1\)，那么 B 必然可以找出 \(e_2 \in T_2\)，满足从 \(T_1\) 中删除 \(e_1\) 加入 \(e_2\) 依然是一个生成树 \(T'_1\)。你感性理解一下，去掉 \(e_1\) 之后原树 \(T_1\) 分成两个点集 \(V_1,V_2\)，由于 \(T_2\) 是一棵树，那么必然有一条边 \(e_2\) 沟通了 \(V_1,V_2\)，不然 \(T_2\) 就不连通了。如果此时 \(e_2\) 未染色，那么 B 可以将 \(e_2\) 染成蓝色，此时 \(T'_1\) 与 \(T_2\) 依然满足上述条件。如果 \(e_2\) 已经染成蓝色，那么 B 随便染蓝一条边也不会使局面更坏。

综上，这种情况下 B 有必胜策略。
如果 \(G\) 中不存在两棵生成树 \(T_1,T_2\)，满足 \(T_1,T_2\) 只由蓝边或无色边组成，并且 \(T_1,T_2\) 中无色边组成的边集不相交。

Ⅰ. 如果 \(G\) 中存在一条边 \(e\) 满足 B 将 \(e\) 染蓝后会得到 1 的局面。那么 R 可将 \(e\) 染红。此时，先手边后手，后手变先手，根据 1 的结论，R 可以染出一棵全红的生成树，B 就染不出一棵全蓝的生成树了。

Ⅱ. 如果 \(G\) 中不存在一条边 \(e\) 满足 B 将 \(e\) 染蓝后会得到 1 的局面。那么 R 可以随便染红一条边，因为 B 不管染蓝哪条边都得不到 1 的局面。

综上，这种情况下 R 有必胜策略。

接下来就是实现的问题。本题数据范围很小，而博主又太菜不会什么 Minmax 搜索之类的高级算法。只好采用暴搜的方法，暴力枚举一棵生成树的边集判断其他边是否能构成一棵生成树，由于 \(C_{30}^9=14307150\) 只达到 \(10^7\) 级别。因此你稍微剪点枝就可以过了。

/*

Contest: -

Problem: HDU 3267

Author: tzc_wk

Time: 2020.7.27

*/

#include <bits/stdc++.h>

using namespace std;

#define fi            first

#define se            second

#define fz(i,a,b)    for(int i=a;i<=b;i++)

#define fd(i,a,b)    for(int i=a;i>=b;i--)

#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)

#define all(a)        a.begin(),a.end()

#define fill0(a)    memset(a,0,sizeof(a))

#define fill1(a)    memset(a,-1,sizeof(a))

#define fillbig(a)    memset(a,0x3f,sizeof(a))

#define fillsmall(a) memset(a,0xcf,sizeof(a))

#define y1            y1010101010101

#define y0            y0101010101010

typedef pair<int,int> pii;

inline int read(){

    int x=0,neg=1;char c=getchar();

    while(!isdigit(c)){

        if(c=='-') neg=-1;

        c=getchar();

    }

    while(isdigit(c)) x=x*10+c-'0',c=getchar();

    return x*neg;

}

bool ans=0;

int n,k,m,u[75],v[75],f[75],num=0;

bool vis[75];

inline int find(int x){

	return (f[x]==x)?(x):find(f[x]);

}

int to[75],ecnt=0,nxt[75],hd[75];

inline void ae(int x,int y){

	to[++ecnt]=y;

	nxt[ecnt]=hd[x];

	hd[x]=ecnt;

}

int used[75];

inline void findcomp(int x){

	if(used[x]) return;

	used[x]=1;

	for(int i=hd[x];i;i=nxt[i]) findcomp(to[i]);

}

inline void dfs(int x,int lst){

    if(x==n){

//		num++;

//		if(num%100000==0) cout<<num<<endl;

//		fz(i,1,m) if(vis[i]) cout<<i<<" ";puts("");

		fill0(hd);fill0(nxt);fill0(to);ecnt=0;fill0(used);

		fz(i,1,m) if(!vis[i]) ae(u[i],v[i]),ae(v[i],u[i]);

		findcomp(1);bool flg=1;

		fz(i,1,n) if(!used[i]) flg=0;

		if(flg) ans=1;

		return;

	}

	for(int i=lst+1;i<=m;i++){

		int _u=u[i],_v=v[i];

//		if(rand()&1)    swap(_u,_v);

		int fu=find(_u),fv=find(_v);

		if(fu!=fv){

			f[fu]=fv;vis[i]=1;dfs(x+1,i);

			if(ans) return;

			vis[i]=0;f[fu]=fu;f[fv]=fv;

		}

	}

}

inline void solve(){

	m=0;fill0(u);fill0(v);fill0(f);

	fz(i,1,k){

		int _u=read(),_v=read();_u++;_v++;

		if(_u!=_v) u[++m]=_u,v[m]=_v;

	}

	fz(i,1,n) f[i]=i;

	fill0(vis);ans=0;dfs(1,0);

	if(ans) puts("YES");

	else puts("NO");

}

signed main(){

	while(scanf("%d %d",&n,&k)){

		if(!~n) break;

		solve();

	}

	return 0;

}

巴特西

HDU 3267 Graph Game（博弈论+图论+暴力）

最新文章

热门文章