chenhongkan的博客

博客

求助！关于一个DAG求任意节点出发的网络规模是多少

2023-03-24 23:37:52 By chenhongkan

给定一个DAG，对于每个节点求两个值第一个值是从该节点开始，可以到达的网络规模节点数量有多少第二个值是该节点与可达节点直接的平均距离是多少？

DAG 求助算法

vfleaking_sb

I don't know

2023-03-25 13:38:05
回复

pink_rabbit

为啥要给差评？UOJ 就是这么对待 2017 年的老用户的？

2023-03-27 20:39:24
回复

asdasdasdasdasd

test

2023-03-29 17:45:47
回复

myee

不太清楚网络规模，但如果只是计算答案，似乎可以用 `bitset` 加速。不妨认为 $|E|=O(|V|^2)$。第一问可以直接用 `bitset` 维护每个点所能走到的点，做到 $O(|V|^2/w)$。第二问考虑暴力 bfs 找最短路，使用 `bitset` 快速找出当前要扩展的节点，做到 $O(|V|^3/w)$。

2023-03-31 09:59:03
回复

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。