BZOJ1040:[ZJOI2008]骑士——题解
2024-08-30 04:27:55
http://www.lydsy.com/JudgeOnline/problem.php?id=1040
题面大意:n个人有一个价值和一个最恨的人,现在组出一个队伍使得价值最大且没有仇恨关系。
————————————————————
如果我们把被仇恨的人向仇恨他的人连一条有向边的话,那么我们不难发现,我们得到的图将会是若干个基环外向树(就是一个环,环上每个点都挂着一棵树)。
如果没有环,只有树的话,那么显然就是“没有上司的舞会”的那道题。
那么基本思路就没有变,f[i][0]表示i不选的时候的最大价值,f[i][1]表示i选的时候的最大价值。
我们显然可以先枚举树在环上的根,然后将环拆开成树,对这棵树进行一遍树形dp。
但是显然拆开部分也需要考虑,我们对拆开的边的另一个端点也进行一次树形dp,这样我们就有了所有的点的真实dp,我们就可以愉快的更新了。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e6+;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct node{
int to;
int nxt;
}edge[N];
int head[N],fa[N],val[N],num[N],cnt=;
ll ans,f[N][];
bool vis[N];
inline void add(int u,int v){
cnt++;
fa[v]=u;
edge[cnt].to=v;
edge[cnt].nxt=head[u];
head[u]=cnt;
return;
}
void dfs(int u){
vis[u]=;
f[u][]=val[u];
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(!vis[v]){
dfs(v);
f[u][]+=max(f[v][],f[v][]);
f[u][]+=f[v][];
}
}
return;
}
inline void dp(int u){
int rt;
for(rt=u;num[rt]!=u;rt=fa[rt])num[rt]=u;
dfs(rt);
u=fa[rt];
f[u][]=f[u][];
for(u=fa[u];u!=rt;u=fa[u]){
f[u][]=;f[u][]=val[u];
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
f[u][]+=max(f[v][],f[v][]);
f[u][]+=f[v][];
}
}
f[rt][]=val[rt];
for(int i=head[rt];i;i=edge[i].nxt){
int v=edge[i].to;
f[rt][]+=f[v][];
}
ans+=max(f[rt][],f[rt][]);
return;
}
int main(){
int n=read();
for(int i=;i<=n;i++){
val[i]=read();
add(read(),i);
}
for(int i=;i<=n;i++){
if(!vis[i])dp(i);
}
printf("%lld\n",ans);
return ;
}
最新文章
- Lind.DDD.UoW~方法回调完成原子化操作
- Windows Internals学习笔记(六)Windows关键系统组件
- A C[HDU1570]
- 分层导航and隐藏导航
- 【python cookbook】【字符串与文本】13.对齐文本字符串
- Java Swing的进化
- 【周全考虑】CodeForces 245B——Internet Address
- java中String类、StringBuilder类和StringBuffer类详解
- 通过Delphi获得qq安装路径
- 解读CSS的背景(background)样式
- 面试题之——将文件夹下java文件写入到新的文件夹,并修改扩展名
- 关于MYSQL存储中文问题
- Go语言的切片
- txt文本文件记录日志
- C#之设计模式之六大原则(转载)
- unittest中的Empty suite错误
- mmap:速度快+整块操作
- presto 判断数据量是否大于一个比较小的值的优化
- 基本功 | Litho的使用及原理剖析
- 前端安全 -- XSS攻击