站长字体,高端网站开发企业,北京网站建公司新闻,专业做网站企业点这里
结论题#x1f605; #xff0c;图一乐
结论#xff1a;如果原图中存在两个边集不交的生成树#xff0c;那么 Bob \text{Bob} Bob必胜#xff1b;否则 Alice \text{Alice} Alice必胜
证明有点难#x1f605;
首先#xff0c;考虑维护两颗 不存在红边 的生成树…点这里
结论题 图一乐
结论如果原图中存在两个边集不交的生成树那么 Bob \text{Bob} Bob必胜否则 Alice \text{Alice} Alice必胜
证明有点难
首先考虑维护两颗 不存在红边 的生成树如果 Alice \text{Alice} Alice断掉了其中一颗树上的一条边将这个树分成两个连通块那么 Bob \text{Bob} Bob一定可以在另一颗树上选择一条边变成蓝色使得这个树再次联通最终两个生成树都只由蓝边构成
其次如果原图中不存在这样的两颗生成树则考虑某次 Alice \text{Alice} Alice操作时 Bob \text{Bob} Bob胜利的条件将所有蓝色的边 复制一遍使得存在两个边集不交的生成树。假设存在某种策略使得 Bob \text{Bob} Bob在某次操作后满足了这个条件那么 Alice \text{Alice} Alice可以照搬 Bob \text{Bob} Bob的策略使得某次操作后将红边复制一遍使得存在两个边集不交的生成树。因此 Alice \text{Alice} Alice存在可以让红边构成一颗生成树的策略。又因为原图中不存在两个边集不交的生成树因此 Bob \text{Bob} Bob无法胜利
有点绞
发现 ( 30 9 ) \binom{30}{9} (930)比较小直接暴搜即可。
#includecstdio
#includeiostream
#define ll long long
#define pb push_back
#define fi first
#define se second
#define db double
#define ull unsigned long long
#define inf 0x3f3f3f3f
using namespace std;
int n,m,fa[10],fa2[10],U[30],V[30],s[30];
int find(int x){return fa[x]x?x:find(fa[x]);
}
int check(){for(int i0;in;i)fa2[i]fa[i],fa[i]i;int tot0;for(int i0;im;i){if(s[i]0){int xfind(U[i]),yfind(V[i]);if(x!y)fa[x]y,tot;}}if(totn-1){return 1;}for(int i0;in;i)fa[i]fa2[i];return 0;
}
int dfs(int x,int y){if(yn-1)return check();for(int ix;im;i){int afind(U[i]),bfind(V[i]);if(ab)continue;fa[a]b,s[i]1;if(dfs(i1,y1))return 1;fa[a]a,s[i]0;}return 0;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);while(cinnm){if(n-1m-1)break;for(int i0;in;i)fa[i]i;for(int i0;im;i)cinU[i]V[i],s[i]0;cout(dfs(0,0)?YES:NO)\n;}
}
