https://www.lydsy.com/JudgeOnline/problem.php?id=4316

题意:给出一张仙人掌图,求最大独立集。

首先,对于一棵树,我们知道它的最大独立集可以dp求出。

f[i][0/1]f[i] [0/1] 表示 不选/选 结点 ii

{f[u][0]=(u,v)Emax(f[v][1],f[v][0])f[u][1]=(u,v)Ef[v][1]\begin{cases} f[u] [0]=\sum_{(u,v)\in E} max(f[v] [1],f[v] [0])\\ f[u] [1]=\sum_{(u,v)\in E} f[v] [1] \end{cases}

然而本题有环,环上两点的最大独立集显然无法这样求出,但若只有一个点属于环,则仍然存在父子之间的dp关系。所以考虑把环单独拿出来考虑。

圆圆点之间的连边与树边相同,而方点表示一个环,所以单独考虑。

方点的 f 值表示与环的最高点(dfs序最小的点)相邻的两个点取或不取。当遇到方点,则把环提取出来,由于栈顶和底之间隔着环的父亲,所以直接单向dp。

由于圆方树是有向树,所以方点的父亲,即环的最高点,此时可以直接利用方点进行转移。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 100003;
int n, m, nn;
vector<int>gg[maxn];
int dfn[maxn];
int cnt;
vector<int>G[maxn << 1];
int fa[maxn];
bool incir[maxn];
void dfs1(int u, int _fa) {
dfn[u] = ++cnt;
for (int i = 0; i < gg[u].size();i++) {
int v = gg[u][i];
if (v == _fa)continue;
if (!dfn[v]) {
fa[v] = u;
dfs1(v, u);
}
else if (dfn[v] < dfn[u]) {
++nn;
G[v].push_back(nn);
incir[v] = true;
fa[nn] = v;
int tmp = u;
while (tmp^v) {
G[nn].push_back(tmp);
incir[tmp] = true;
tmp = fa[tmp];
}
}
}
if (!incir[u])G[fa[u]].push_back(u);
}
int f[maxn<<1][2], dp[maxn<<1][2];
int st[maxn];
void solve(int u) {
int top = 0;
for (int i = 0; i < G[u].size();i++) {
int v = G[u][i];
st[++top] = v;
}
dp[1][0] = f[st[1]][0]; dp[1][1] = -INF;
for (int i = 2; i <= top; i++) {
dp[i][1] = dp[i - 1][0] + f[st[i]][1];
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + f[st[i]][0];
}
f[u][0] = dp[top][0];
dp[top + 1][0] = dp[top + 1][1] = 0;
for (int i = top; i >= 1; i--) {
dp[i][1] = dp[i + 1][0] + f[st[i]][1];
dp[i][0] = max(dp[i + 1][0], dp[i + 1][1]) + f[st[i]][0];
}
f[u][1] = max(dp[1][0], dp[1][1]);
}
void dfs2(int u) {
f[u][0] = 0; f[u][1] = 1;
for (int i = 0; i < G[u].size();i++) {
int v = G[u][i];
dfs2(v);
if (u <= n) {
f[u][0] += max(f[v][0], f[v][1]);
f[u][1] += f[v][0];
}
}
if (u > n) {
solve(u);
}
}
int main() {
scanf("%d%d", &n, &m);
nn = n;
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
gg[u].push_back(v);
gg[v].push_back(u);
}
dfs1(1, 0);
dfs2(1);
cout << max(f[1][0], f[1][1]) << endl;
return 0;
}