【luogu AT2376】Black and White Tree（结论）（博弈论）（二分图）Black and White Tree

140 阅读 0 评论 93 点赞

我是靠谱客的博主天真人生，这篇文章主要介绍【luogu AT2376】Black and White Tree（结论）（博弈论）（二分图）Black and White Tree，现在分享给大家，希望可以做个参考。

Black and White Tree

题目链接：luogu AT2376

题目大意

给你一棵树，每次先手后手轮流选一个点染上自己的颜色。
然后如果先手的一次染色中它染色的点连着的边都是先手染过色的，那先手就赢了。
然后要你判断是先手必胜还是后手必胜。

思路

这题的结论是如果这个图的最大匹配能覆盖所有点，就是后手必胜，否则是先手必胜。

下面简单证明：如果有最大匹配是全部点，那先手无论点什么点，后手只要点跟它匹配的点。
那因为是匹配，是相邻的点，所以所有的白点旁边一定会有点都是黑点。（跟它匹配的点）

那如果最大匹配不是整个图，就会多出一个点。
我们可以安排这个点的位置到叶子节点，然后先手把它连着的点点了，后手不能叶子结点点，而是要点你那个点匹配的点（否则你别的地方就可以成立了），然后你就可以点这个叶子结点赢了。

然后判断树的最大匹配可以树形 DP，也可以直接无脑黑白染色网络流。

代码

复制代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define INF 0x3f3f3f3f3f3f3f3f 
using namespace std;
struct node {
int to, nxt;
}e[200001];
int n, x, y, deg[200001];
int num[2], le[200001], KK;
struct nde {
int x, to, nxt, op;
}e_[600001];
int le_[200005], KK_, S, T;
int dis[200005];
void add(int x, int y) {
e[++KK] = (node){y, le[x]}; le[x] = KK;
e[++KK] = (node){x, le[y]}; le[y] = KK;
}
void add_(int x, int y, int z) {
e_[++KK_] = (nde){z, y, le_[x], KK_ + 1}; le_[x] = KK_;
e_[++KK_] = (nde){0, x, le_[y], KK_ - 1}; le_[y] = KK_;
}
void dfs(int now, int father) {
deg[now] = deg[father] + 1;
if (deg[now] & 1) {
add_(S, now, 1);
add_(now, father, 1);
for (int i = le[now]; i; i = e[i].nxt)
if (e[i].to != father)
add_(now, e[i].to, 1);
}
else add_(now, T, 1);
for (int i = le[now]; i; i = e[i].nxt)
if (e[i].to != father) dfs(e[i].to, now);
}
bool bfs() {//网络流求最大匹配（其实也可以 DP）
memset(dis, 0x7f, sizeof(dis));
dis[S] = 0;
queue <int> q;
q.push(S);
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = le_[now]; i; i = e_[i].nxt)
if (e_[i].x && dis[e_[i].to] > dis[now] + 1) {
dis[e_[i].to] = dis[now] + 1;
if (e_[i].to == T) return 1;
q.push(e_[i].to);
}
}
return 0;
}
int dfss(int now, int sum) {
if (now == T) return sum;
int go = 0;
for (int i = le_[now]; i; i = e_[i].nxt)
if (dis[e_[i].to] == dis[now] + 1 && e_[i].x) {
int this_go = dfss(e_[i].to, min(sum - go, e_[i].x));
if (this_go) {
e_[i].x -= this_go;
e_[e_[i].op].x += this_go;
go += this_go;
if (go == sum) return go;
}
}
return go;
}
int dinic() {
int re = 0;
while (bfs())
re += dfss(S, INF);
return re;
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
scanf("%d %d", &x, &y);
add(x, y);
}
S = n + 1; T = S + 1;
dfs(1, 0);
if (n & 1) {
printf("Firstn");
return 0;
}
if (dinic() * 2 != n) {
printf("Firstn");
}
else printf("Secondn");
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define INF 0x3f3f3f3f3f3f3f3f 
using namespace std;
struct node {
int to, nxt;
}e[200001];
int n, x, y, deg[200001];
int num[2], le[200001], KK;
struct nde {
int x, to, nxt, op;
}e_[600001];
int le_[200005], KK_, S, T;
int dis[200005];
void add(int x, int y) {
e[++KK] = (node){y, le[x]}; le[x] = KK;
e[++KK] = (node){x, le[y]}; le[y] = KK;
}
void add_(int x, int y, int z) {
e_[++KK_] = (nde){z, y, le_[x], KK_ + 1}; le_[x] = KK_;
e_[++KK_] = (nde){0, x, le_[y], KK_ - 1}; le_[y] = KK_;
}
void dfs(int now, int father) {
deg[now] = deg[father] + 1;
if (deg[now] & 1) {
add_(S, now, 1);
add_(now, father, 1);
for (int i = le[now]; i; i = e[i].nxt)
if (e[i].to != father)
add_(now, e[i].to, 1);
}
else add_(now, T, 1);
for (int i = le[now]; i; i = e[i].nxt)
if (e[i].to != father) dfs(e[i].to, now);
}
bool bfs() {//网络流求最大匹配（其实也可以 DP）
memset(dis, 0x7f, sizeof(dis));
dis[S] = 0;
queue <int> q;
q.push(S);
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = le_[now]; i; i = e_[i].nxt)
if (e_[i].x && dis[e_[i].to] > dis[now] + 1) {
dis[e_[i].to] = dis[now] + 1;
if (e_[i].to == T) return 1;
q.push(e_[i].to);
}
}
return 0;
}
int dfss(int now, int sum) {
if (now == T) return sum;
int go = 0;
for (int i = le_[now]; i; i = e_[i].nxt)
if (dis[e_[i].to] == dis[now] + 1 && e_[i].x) {
int this_go = dfss(e_[i].to, min(sum - go, e_[i].x));
if (this_go) {
e_[i].x -= this_go;
e_[e_[i].op].x += this_go;
go += this_go;
if (go == sum) return go;
}
}
return go;
}
int dinic() {
int re = 0;
while (bfs())
re += dfss(S, INF);
return re;
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
scanf("%d %d", &x, &y);
add(x, y);
}
S = n + 1; T = S + 1;
dfs(1, 0);
if (n & 1) {
printf("Firstn");
return 0;
}
if (dinic() * 2 != n) {
printf("Firstn");
}
else printf("Secondn");
return 0;
}