『毒瘤算法系列13』情报传递

本文主要是介绍『毒瘤算法系列13』情报传递，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$

有一个情报网共有$n$个人，通过有向的电话线联络。为保证通信安全，需要满足一些要求，这些要求分为两类：

• ①从第$a$个人通过一条或多条电话线可以联系到第$b$个人；
• ②从第$a$个人通过一条或多条电话线不能联系到第$b$个人。

现在作为总工程师的你需要构造一个合法的情报网，使得这个情报网满足给定要求，或者告诉情报机构这样的情报网是不存在的。

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

这道题$a$如果到$b$的情况一定满足的话，一定要在满足这对条件的情况下，其它对尽量难以到达，这是一种贪心的最优策略。因此我们只要将$①$中的边连接起来，在判断$②$是否合法即可。

那么我们如何判断合法呢？显然我们只需要用tarjan缩点判断A能否到达B即可。判断方法就是用数组暴力标记，类似于二维的DP:$f[i][j]$表示当前节点$i$是否是节点$j$所能到达的。

这样转移的复杂度是不优秀的：$O(n^2)$.

由于这只是0/1状态，如果我们使用bitset中的或操作，复杂度可以优化到： O ( n

这篇关于『毒瘤算法系列13』情报传递的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---