每个骑士有战斗力和另一个自己厌恶的骑士. 选出一个骑士集合, 使得不存在一个骑士和他厌恶的人同在集合中, 且战斗力之和最大. 求最大战斗力. (骑士数目n≤10^6, 战斗力是不大于10^6的正整数) 所有的边实际上是无向边. 这个定义似曾相识 - 最大权独立集! 它是 NP-hard Problem, 因此本题必有特殊之处. 发现点数和边数相 - 环套树? 把环找出来, 每个子树DP一下, 再对环DP一下. 首尾相互制约, 怎么处理呢? 把环从任意位置断开, 强制第一个点选或不选, 各跑一次DP.
然后WA......这么短的代码都写错? TAT 还是哪一步的分析出了问题?
对拍一下. 还没点开输入文件, 就想到, 为什么认定这是一个环套树呢? 两个分离的三元环, 也有6个点和6条边. 输入是一个环套树森林.
看了看别人的做法, 比我的简单多了......环套树的环从任意位置断开, 就形成了一棵树. 设断开的边是(u,v), 分别以u,v为根, 并强制根不选, 各跑一遍DP即可.
最后, 说一说怎么找环. 我们可能会混淆二元环和邻接表处理无向图时正反各加入一次的边, 但是这样做可以避免这个问题: 记录每个点的发现时间dfn[u]
, 和它在DFS树上的父亲fa[u]
. 如果u,v有边, v还没访问过, 则访问v; 否则, 如果dfn[v]>dfn[u]
, 说明(v,u)
是一条返祖边, 顺着fa
即可找到整个环. 注意, fa[u]
只是u在这棵DFS树上的父亲, 后面对每棵子树跑DP时就不能用了.
typedef long long ll;
const int N = 1e6;
const ll inf = 1e13;
bool ban[N];
int dfs_clock, m, dfn[N], fa[N], c[N], cir[N];
ll f[2][N], g[2][N];
vector<int> adj[N];
void dfs(int u)
{
dfn[u] = ++dfs_clock;
rep (i, 0, adj[u].size()) {
int v = adj[u][i];
if (!dfn[v]) {
fa[v] = u;
dfs(v);
} else if (dfn[v] > dfn[u]) {
do {
ban[cir[m++] = v] = true;
v = fa[v];
} while (v != u);
ban[cir[m++] = v] = true;
}
}
}
void dp_on_tree(int u, int p)
{
f[1][u] = c[u];
rep (i, 0, adj[u].size()) {
int v = adj[u][i];
if (v == p || ban[v]) continue;
dp_on_tree(v, u);
f[1][u] += f[0][v];
f[0][u] += max(f[0][v], f[1][v]);
}
}
void dp_on_circle()
{
rep (i, 1, m) {
int v = cir[i];
g[0][i] = f[0][v] + max(g[0][i-1], g[1][i-1]);
g[1][i] = f[1][v] + g[0][i-1];
}
}
int main()
{
int n;
scanf("%d", &n);
rep (i, 0, n) {
int j;
scanf("%d%d", c+i, &j);
--j;
adj[i].push_back(j);
adj[j].push_back(i);
}
ll sum = 0;
rep (v, 0, n) {
if (dfn[v]) continue;
m = 0;
dfs(v);
rep (i, 0, m)
dp_on_tree(cir[i], -1);
g[0][0] = f[0][cir[0]];
g[1][0] = -inf;
dp_on_circle();
ll ans = max(g[0][m-1], g[1][m-1]);
g[0][0] = -inf;
g[1][0] = f[1][cir[0]];
dp_on_circle();
ans = max(ans, g[0][m-1]);
sum += ans;
}
printf("%lld\n", sum);
return 0;
}