网站utf8乱码,金华自助建站,手机网站cms有哪些,网站推广平台有哪些解析
一直在路径可逆上做功夫#xff0c;跑偏了。
题目可以转化为一个模型#xff1a;给出一张无向图#xff0c;每次可以移动到未移动过的点上#xff0c;不能移动者判负。
这个的做法就是判断是否完美匹配#xff0c;完美匹配则后手必胜#xff0c;否则先手必胜。
…解析
一直在路径可逆上做功夫跑偏了。
题目可以转化为一个模型给出一张无向图每次可以移动到未移动过的点上不能移动者判负。
这个的做法就是判断是否完美匹配完美匹配则后手必胜否则先手必胜。
存在完美匹配的话每次后手只需要移动到对应的匹配点即可如果不存在先手放在一个失配点上后手必然不可能再走到失配点了否则就会出现增广路不再是最大匹配。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define ldb long double
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
using namespace std;const int N2e5100;
const int inf1e9;
const int mod998244353;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}inline ll ksm(ll x,ll k){ll res(1);while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}int n,m;vectorinte[N];
int dp[N];
void dfs(int x,int fa){for(int to:e[x]){if(tofa) continue;dfs(to,x);dp[x]dp[to];}dp[x]?dp[x]-1:dp[x]1;return;
}signed main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifnread();for(int i1;in;i){int xread(),yread();e[x].push_back(y);e[y].push_back(x);}dfs(1,0);if(dp[1]) puts(Alice);else puts(Bob);return 0;
}
/*
*/
