AcWing 285. 没有上司的舞会(公司之斗)
原题链接
简单
作者:
橙外
,
2021-02-05 16:14:42
,
所有人可见
,
阅读 5604
本公司暗地里的斗争......
董事长来不来已经决定了————
一切
#include <iostream>
#include <algorithm>
using namespace std;
#define N 6010
bool vis[N]; // 判断此小弟是否有上司
int head[N],cnt;
int f[N][2],happy[N],n;
struct edge
{
int to,nex;
}e[N];
void add(int from,int to)
{
e[++cnt] = (edge){to,head[from]};
head[from] = cnt;
}
void dfs(int boss)
{
f[boss][1] = happy[boss]; // 1代表这个boss要来,先加上他来的利益
for (int i = head[boss]; i; i = e[i].nex)
{
int too = e[i].to;
dfs(too); // 递归一直搜
f[boss][0] += max(f[too][0] , f[too][1]); // boss不来,那小弟就是王了,但小弟要以利益为重,如果小小弟来可以获利更大,就让小小弟来
f[boss][1] += f[too][0]; // boss来了!!!小弟都承让
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> happy[i];
for (int i = 1; i <= n - 1; i++)
{
int a,b;
cin >> a >> b;
add(b , a);
vis[a] = true; // a有上司了(以后出行要小心)
}
int root = 1;
while (vis[root]) root ++; // 找到根节点(没有上司的董事长)
dfs(root);
cout << max(f[root][0] , f[root][1]);// 取董事长来和不来的最大利益
return 0;
}
题目推荐
小说一般精彩的注释,我竟然看懂了
tql!
能看懂就是我的荣幸
BOSS致平😅😅
hh,BOSS帮小弟做决定
妈的 给力
hh
我肖神马上就看到这里了
代码太短不够看, 建议搞个2百行
天,作者真的好可爱
head数组表示啥
链式前向星
笑死😆
6
大佬NB!
Orz
hh
orz
orz
%%%