AtCoder Grand Contest 014 D - Black and White Tree 博弈论题意分析代码

113 阅读 0 评论 75 点赞

我是靠谱客的博主活泼酒窝，这篇文章主要介绍AtCoder Grand Contest 014 D - Black and White Tree 博弈论题意分析代码，现在分享给大家，希望可以做个参考。

题意

给你一棵树，先手后手轮流操作，每次先手可以把某个未染色节点染白，后手可以把某个未染色节点染黑。等没有未染色节点时，所有与黑点相邻的白色点都会变黑，若仍存在白点，则先手胜，反之则后手胜。
n<=100000

分析

结论：若存在完美匹配的后手必胜，否则先手必胜。
证明：若存在完美匹配，无论先手染哪一个点，后手必然可以染该点的匹配点，从而后手必胜。
若不存在完美匹配，则必然有至少一个叶节点存在于最大匹配中。先手可以每次找一个存在于最大匹配中的叶节点，将其相邻节点染白，则黑点必然只能染该叶节点。因为没有完美匹配，所以到最后必然会剩下至少一个未匹配点，满足其相邻节点都被染成了白色且当前先手操作。所以先手必胜。

代码

复制代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005;

int n,cnt,last[N],f[N],g[N];
struct edge{int to,next;}e[N*2];

int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void addedge(int u,int v)
{
    e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
    e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}

void dp(int x,int fa)
{
    int mx=-n;
    for (int i=last[x];i;i=e[i].next)
    {
        if (e[i].to==fa) continue;
        dp(e[i].to,x);
        g[x]+=max(g[e[i].to],f[e[i].to]);
        mx=max(mx,g[e[i].to]-f[e[i].to]);
    }
    if (mx>=0) f[x]=g[x]+1;
    else if (mx>-n) f[x]=g[x]+mx+1;
}

int main()
{
    n=read();
    for (int i=1;i<n;i++)
    {
        int x=read(),y=read();
        addedge(x,y);
    }
    dp(1,0);
    if (max(f[1],g[1])==n/2&&!(n&1)) puts("Second");
    else puts("First");
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100005;

int n,cnt,last[N],f[N],g[N];
struct edge{int to,next;}e[N*2];

int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void addedge(int u,int v)
{
    e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
    e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}

void dp(int x,int fa)
{
    int mx=-n;
    for (int i=last[x];i;i=e[i].next)
    {
        if (e[i].to==fa) continue;
        dp(e[i].to,x);
        g[x]+=max(g[e[i].to],f[e[i].to]);
        mx=max(mx,g[e[i].to]-f[e[i].to]);
    }
    if (mx>=0) f[x]=g[x]+1;
    else if (mx>-n) f[x]=g[x]+mx+1;
}

int main()
{
    n=read();
    for (int i=1;i<n;i++)
    {
        int x=read(),y=read();
        addedge(x,y);
    }
    dp(1,0);
    if (max(f[1],g[1])==n/2&&!(n&1)) puts("Second");
    else puts("First");
    return 0;
}