首页 > 间谍网络
开通博客写题解
头像 威风镰鼬
发表于 2021-08-13 10:39:48
思路 这道题中，图的遍历起点必然是可控制的，如果起点不可控制，答案肯定是NO,NO的情况只需要从1~n找到第一个没被遍历过的数输出就可以了。因此，我们记录下每个节点的入度，那么就相当于从图中所有入度为0（且可以控制）的点开始拓扑排序，并记录访问节点即可。但是题目不保证是有向无环图，因此我们需要对环进 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Holland_Pig
发表于 2019-08-16 22:40:57
第一次用写题解qwqqwq 首先求出是否有点不能被访问 若有则显然这个间谍不能被控制 然后就是强连通分量问题 对于一个强连通分量我们贪心的选取其中花费最小的点统计答案 最终答案为入度为的点的花费和 不得不说代码量还挺大... 有一点要注意 边的数量应该是而不是和n同样大小，分的大多数是边表没开够吧. 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”