首页 > 代码库 > 繁华模拟赛 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的博弈游戏