首页 > 代码库 > 繁华模拟赛 David与Vincent的博弈游戏
繁华模拟赛 David与Vincent的博弈游戏
#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>using namespace std;const int maxn = 100005;struct edge{ int to; int nxt;};int n,g[maxn],dep[maxn],dpd[maxn],dpv[maxn];int head[maxn],cnt;edge e[maxn];inline void add_edge(int u,int v){ cnt++; e[cnt].to = v; e[cnt].nxt = head[u]; head[u] = cnt;}void input(){ cin>>n; int u,v; for(int i = 1;i < n;i++){ scanf("%d%d",&u,&v); add_edge(u,v); }}void dfs(bool dep,int x){ if(!head[x]){ dpd[x] = dpv[x] = g[x] = 1; return; } for(int i = head[x];i;i = e[i].nxt){ dfs(!dep,e[i].to); g[x] += g[e[i].to]; } dpv[x] = dpd[x] = 1; if(dep){ int sum = 0; for(int i = head[x];i;i = e[i].nxt){ sum += dpv[e[i].to] - 1; dpd[x] = max(dpd[x],g[x]-g[e[i].to]+dpd[e[i].to]); } dpv[x] = max(dpv[x],sum+1); }else{ int sum = 0; for(int i = head[x];i;i = e[i].nxt){ sum += dpd[e[i].to] - 1; dpv[x] = max(dpv[x],g[x]-g[e[i].to]+dpv[e[i].to]); } dpd[x] = max(dpd[x],sum+1); }}int main(){ freopen("game.in","r",stdin); freopen("game.out","w",stdout); input(); dfs(true,1); cout<<dpd[1]<<" "<<g[1] - dpv[1] + 1; return 0;}#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#include<cmath>#include<vector>#include<queue>#include<map>#include<set>#include<stack>#include<cstdlib>#include<string>#include<bitset>#define INF 1000000000#define N 200005#define fi first#define se second#define debug(x) cout<<#x<<"="<<x<<endl#define MP(x,y) make_pair(x,y)using namespace std;typedef long long LL;typedef pair<int,int> pii;int dp[N],fa[N],lf[N],m;vector<int> G[N];void dfs1(int x,int d){ int v,i; if(d==1) dp[x]=INF; else dp[x]=0; for(i=0;i<G[x].size();i++) { v=G[x][i]; if(fa[x]!=v) { lf[x]=1; fa[v]=x; dfs1(v,d^1); if(d==1) dp[x]=min(dp[x],dp[v]); else dp[x]+=dp[v]; } } if(!lf[x]) dp[x]=1,m++;}void dfs2(int x,int d){ int v,i; if(d==1) dp[x]=0; else dp[x]=INF; for(i=0;i<G[x].size();i++) { v=G[x][i]; if(fa[x]!=v) { lf[x]=1; fa[v]=x; dfs2(v,d^1); if(d==1) dp[x]+=dp[v]; else dp[x]=min(dp[x],dp[v]); } } if(!lf[x]) dp[x]=1; //debug(x); //debug(dp[x]);}int main(){ int n,i,a,b; freopen("game.in","r",stdin); freopen("game.out","w",stdout); cin>>n; for(i=1;i<n;i++) { scanf("%d%d",&a,&b); G[a].push_back(b); //G[b].push_back(a); } dfs1(1,1); cout<<m-dp[1]+1<<‘ ‘; dfs2(1,1); cout<<dp[1]<<endl; return 0;}// davidlee1999WTK 2015/// srO myk Orz//ios::sync_with_stdio(false);
繁华模拟赛 David与Vincent的博弈游戏
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。