洛谷 P2607 [ZJOI2008] 骑士-提高+/省选-

题目描述

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

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

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

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

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

输入格式

第一行包含一个整数 $n$，描述骑士团的人数。

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

输出格式

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

输入输出样例 #1

输入 #1

3
10 2
20 3
30 1

输出 #1

30

说明/提示

数据规模与约定

对于 $30\%$ 的测试数据，满足 $n\le 10$；

对于 $60\%$ 的测试数据，满足 $n\le 100$；

对于 $80\%$ 的测试数据，满足 $n\le 10^4$。

对于 $100\%$ 的测试数据，满足 $1\le n\le 10^6$，每名骑士的战斗力都是不大于 $10^6$ 的正整数。

solution

题目大意：基环森林中，不相邻点的距离和的最大值
思路：

• 找到环上的某个点 u
• 以 u 和其父节点 fa[u] 为根节点树上 dp 计算 f[i], g[i] ,即包含本节点的子树最大和和不含本节点的子树最大和
• 结果为 $\sum (max(g[u],g[fa[u]])$ 其中 u 为每个基环树中环上取一个点

代码

#include<iostream>
#include<vector>
#include "algorithm"
#include "cstring"using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6 + 5, M = 1e9 + 7;int n, fa[N], vis[N], a[N];ll f[N], g[N];vector<int> e[N];int find_u(int u) {vis[u] = 1;return vis[fa[u]] ? u : find_u(fa[u]);
}void dp(int u, int p) {vis[u] = 1;for (int v: e[u]) {if (v == p) continue; // p 是起点，相当于断开了起点和其fa的边dp(v, p);f[u] += g[v];g[u] += max(f[v], g[v]);}f[u] += a[u];
}/** 1 反向建图，形成外向基环树* 2 找到环上一个点 u, 以 u 为根节点进行树上 dp*      f[u]:包含本节点的最大值*      g[u]:不包含本节点的最大值* 3 以 fa[u] 为根节点进行树上 dp*      max(g[u], g[fa])*/int main() {cin >> n;for (int i = 1; i <= n; i++) {scanf("%d%d", a + i, fa + i);// cin >> a[i] >> fa[i]; // 反向建图，形成外向基环树e[fa[i]].push_back(i);}ll ans = 0; for (int i = 1; i <= n; i++) {if (!vis[i]) {ll Max = 0;int u = find_u(i);dp(u, u);Max = max(Max, g[u]);memset(f, 0, sizeof f);memset(g, 0, sizeof g);dp(fa[u], fa[u]);Max = max(Max, g[fa[u]]);ans += Max;}}cout << ans << endl;return 0;
}

结果