【解题报告】BZOJ 1040 [ZJOI2008] 骑士

发表于

传送门

$\text{Description}$

在基环树上求解最大点独立集问题。

有点学术啊。那我先来解释一下吧。

基环树

基环树 顾名思义，就是基于一个环上的树，也就是一个树中有一个环。由于原题中把骑士看成结点，憎恨关系看成边之后就得到了一个有 $n$ 个结点， $n$ 条边的图，我们知道由 $n$ 个结点， $n - 1$ 条边组成的连通图是一棵树。那么拥有 $n$ 个结点和 $n$ 条边的连通图就是一棵基环树。这样一来，原题的图就可以抽象成一个基环树森林。

最大点独立集

一个图的点独立集是原图总点集的一个子集，且点独立集中任意两个顶点均不相邻。简单点来说就是从图中挑点，所取的点两两不相邻。

图的最大点独立集就是顶点数最多的点独立集。

但是本题是带点权的，这样一来就要稍微更改一下定义，我们定义图的最大带权点独立集就是总权重（集合中所有点的权重的和）最大的点独立集。

$\text{Solution}$

假如这是个森林的话就很简单，就是 没有上司的舞会 。

这里面详细介绍了怎样解决树上的最大点独立集问题，这里就不再赘述。

但是带权的话，状态转移方程就要修改一下：

我们定义 $d(i, 0)$ 表示在以 $i$ 为根的子树中，不取 $i$ 所能达到的最大权重。

相应的，$d(i, 1)$ 表示以 $i$ 为根的子树中，取 $i$ 所能达到的最大权重。

由于上面的转移方程是对付树的，基环树又是树的特殊变种（基环树不是树）。考虑怎样对基环树进行处理使之可以用上面的方法解决。

考虑到基环树删去环上的一条边就变成了一棵树（含有 $n$ 个结点及 $n - 1$ 条边且保证连通）。

我们就可以设计出一个算法：找到这个基环树中的环，并找到其上任意一条边 $(u, v)$ （所有边的地位等同），然后把它“删掉”（在dp过程中不经过这条边），让它变成一棵树，接下来我们考虑添加这条边对结果的影响。

很显然，多了这条边， $u$ 和 $v$ 不可以同时选取，这样子就会有三种情况：

  • 选 $u$ , 不选 $v$
  • 选 $v$，不选 $u$
  • 既不选 $u$ 也不选 $v$

但是这样是很难处理的。我们可以考虑合并成两种情况：

  • 不选 $u$ , $v$ 随意
  • 不选 $v$ , $u$ 随意

这样就可以解决问题了。

我们在solve完 $u$ 结点之后，保存 $p = d(u, 0)$ ，再solve $v$ 结点，保存 $q = d(v, 0)$ 再取 $\max{p, q}$ 加入 $Ans$ 即可。这样一来就保证了 $u$ 和 $v$ 不会同时选中，也保证了解的最优性。

$\text{Code}$

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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 1000010
#define max(x, y) ((x) > (y) ? (x) : (y))
int value[MAXN], a, b;
long long f[MAXN][2];
struct edgeType {
    int to, next;
} edge[MAXN << 1];
int head[MAXN], vis[MAXN], n, s, x, y, cut;
void addEdge(int from, int to) {
    static int cnt = 0;
    edge[cnt] = (edgeType){to, head[from]};
    head[from] = cnt++;
}
void findCycle(int u, int p) {
    vis[u] = 1;
    for (int i = head[u]; ~i; i = edge[i].next) {
        if ((i ^ 1) == p) continue;
        int v = edge[i].to;
        if (vis[v]) {
            x = u, y = v;
            cut = i;
            continue;
        }
        findCycle(v, i);
    }
}
void solve(int u, int p) {
    f[u][0] = 0;
    f[u][1] = value[u];
    for (int i = head[u]; ~i; i = edge[i].next) {
        if ((i ^ 1) == p) continue;
        if (i == cut || (i ^ 1) == cut)
            continue;
        int v = edge[i].to;
        dfs(v, i);
        f[u][1] += f[v][0];
        f[u][0] += max(f[v][1], f[v][0]);
    }
}
int main() {
    memset(head, -1, sizeof head);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a, &b);
        addEdge(i, b);
        addEdge(b, i);
        value[i] = a;
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        findCycle(i, -2);
        solve(x, -1);
        long long temp = f[x][0];
        solve(y, -1);
        temp = max(temp, f[y][0]);
        ans += temp; 
    }
    printf("%lld", ans);
    return 0;
}