P2607 [ZJOI2008]骑士

[ZJOI2008]骑士

题目描述

Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。

最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。

骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。

战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。

为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。

输入输出格式

输入格式：

输入文件knight.in第一行包含一个正整数N，描述骑士团的人数。

接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。

输出格式：

输出文件knight.out应包含一行，包含一个整数，表示你所选出的骑士军团的战斗力。

输入输出样例

输入样例#1：

输出样例#1：

说明

对于30%的测试数据，满足N ≤ 10；

对于60%的测试数据，满足N ≤ 100；

对于80%的测试数据，满足N ≤ 10 000。

对于100%的测试数据，满足N ≤ 1 000 000，每名骑士的战斗力都是不大于 1 000 000的正整数。

分析

首先这道题与没有上司的舞会很类似。如果这道题的关系图是一颗树，那么就是入门树形DP，求最大权值的独立集

$s(u) = sumlimits_{v}^{v是u的儿子}$

$g(u) = sumlimits_{v}^{v是u的孙子}$

$f(u) = max(s(u), g(u)+val[u])$

$s (u) = \sum_{v}^{v 是 u 的儿子} f (v)$

但是本题又有所不同。没有上司的舞会中，题目保证了关系图是一颗树，因为不可能下属的下属是上司。

但是本题中，每个骑士都有且只有一个自己痛恨的人，骑士本身并不存在地位高低，因此可以1仇视2，2仇视1，或者1仇视2，2仇视3，3仇视1。

这样会形成一个环，就不能用普通的树形DP去解了。

那么这道题的关系图是什么样的呢？

基环树

基环树了解一下。

树大家都知道，比如这个样。

而基环树长这个样

也就是说，在树的基础上加一条边使之出现一个环。

根据基环树的边的方向（点的出度入度），我们还可以将基环树分出两类。

一类是基环内向树。特点是每个点都有且只有一个出度，并且环外的节点方向指向环内。

还有一类是基环外向树，与基环内向树对应，它有且只有一个入度，并且由环指向环外。

本题中每个骑士间的关系图就是一个基环树。

题中说，每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己）

首先排除自环的可能性。

如果你把骑士指向自己厌恶的骑士连一条边，就是一个基环内向树。

（当然如果你把骑士自己厌恶的骑士指向自己连一条边也可以构成一个基环外向树）

很明显满足每个点出度为1的性质。

基环树的一个重要性质是，在一个环中，只有根节点有机会形成环。（其他节点的出度已经供献在建树上了，只有根节点指向它的儿子）

那么对于这个基环树所形成的一个联通块内，有且仅有一个简单链式环。

考虑把基环树上每个联通块都删去一条边，那么它就变成了一棵普通树。

注意根据题意，断环的两个点不能同时选（因为两者中有一者仇视另一者）

那么强制这一个点不选，那一个点选，跑一遍DP，再强制这个点选，那个点不选，跑一遍DP，更新答案

code

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 const int MAXN = 2000010;
10 const LL INF = 9223372036854775806ll;
11 int N, val[MAXN];
12 int head[MAXN], ecnt;
13 int u, fa[MAXN];
14 bool vis[MAXN];
15 LL f[MAXN][2], ans;
16 
17 struct Edge{
18     int node, next;
19 }e[MAXN];
20 
21 inline int read() {
22     int num = 0, f = 1; char ch = getchar();
23     while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
24     while (isdigit(ch)) { num = num * 10 + ch - '0'; ch = getchar(); }
25     return num * f;
26 }
27 
28 inline void Add_Edge(int x, int y) {
29     e[++ecnt].node = y; 
30     e[ecnt].next = head[x]; 
31     head[x] = ecnt;
32 }
33 
34 void doit(int x) {
35     vis[x] = true;
36     f[x][0] = 0; 
37     f[x][1] = val[x];
38     int v;
39     for (int i = head[x]; i ; i = e[i].next) {
40         v = e[i].node;
41         if (v != u) {
42             doit(v);
43             f[x][0] += max(f[v][1], f[v][0]);
44             f[x][1] += f[v][0];
45             //没有上司的舞会模型
46         }
47         else f[v][1] = -INF;
48         //
49     }
50 }
51 
52 void find(int x) {
53     vis[x] = true;
54     u = x;
55     while(!vis[fa[u]]) { 
56         vis[u] = true;
57         u = fa[u];
58     }
59     doit(u);
60     LL t = max(f[u][0], f[u][1]);
61     vis[u] = true;
62     u = fa[u];
63     doit(u);
64     ans += max(t, max(f[u][0], f[u][0]));
65     return ;
66 }
67 
68 int main() {
69     N = read();
70     int x;
71     for (int i = 1; i <= N; ++ i) {
72         val[i] = read(); x = read();
73         Add_Edge(x, i); fa[i] = x;
74     }
75     for (int i = 1; i <+ N; ++ i)
76         if (!vis[i]) find(i);
77     printf("%lld
", ans);
78     return 0;
79 }