【学习笔记】POJ 3834 graph game

点这里

结论题😅 ，图一乐

结论：如果原图中存在两个边集不交的生成树，那么$\text{Bob}$必胜；否则$\text{Alice}$必胜

证明有点难😅

首先，考虑维护两颗 不存在红边 的生成树，如果$\text{Alice}$断掉了其中一颗树上的一条边，将这个树分成两个连通块，那么$\text{Bob}$一定可以在另一颗树上选择一条边变成蓝色，使得这个树再次联通，最终两个生成树都只由蓝边构成

其次，如果原图中不存在这样的两颗生成树，则考虑某次$\text{Alice}$操作时，$\text{Bob}$胜利的条件：将所有蓝色的边 复制一遍，使得存在两个边集不交的生成树。假设存在某种策略，使得$\text{Bob}$在某次操作后满足了这个条件，那么$\text{Alice}$可以照搬$\text{Bob}$的策略，使得某次操作后将红边复制一遍，使得存在两个边集不交的生成树。因此$\text{Alice}$存在可以让红边构成一颗生成树的策略。又因为原图中不存在两个边集不交的生成树，因此$\text{Bob}$无法胜利

有点绞

发现$\left(\genfrac{}{}{0ex}{}{30}{9}\right)$比较小，直接暴搜即可。

#include<cstdio>
#include<iostream>
#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 i=0;i<n;i++)fa2[i]=fa[i],fa[i]=i;int tot=0;for(int i=0;i<m;i++){if(s[i]==0){int x=find(U[i]),y=find(V[i]);if(x!=y)fa[x]=y,tot++;}}if(tot==n-1){return 1;}for(int i=0;i<n;i++)fa[i]=fa2[i];return 0;
}
int dfs(int x,int y){if(y==n-1)return check();for(int i=x;i<m;i++){int a=find(U[i]),b=find(V[i]);if(a==b)continue;fa[a]=b,s[i]=1;if(dfs(i+1,y+1))return 1;fa[a]=a,s[i]=0;}return 0;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);while(cin>>n>>m){if(n==-1&&m==-1)break;for(int i=0;i<n;i++)fa[i]=i;for(int i=0;i<m;i++)cin>>U[i]>>V[i],s[i]=0;cout<<(dfs(0,0)?"YES":"NO")<<"\n";}
}