CodeVS&Luogu 间谍网络

这个题大概思路就是一发裸的Tarjan然后建一个缩点的图。

读入之后先来一发Tarjan(注意有可能有多个连通图),记录下每个点属于的强连通分量。

然后缩点,建一个DAG,这时根据DAG的结构,肯定存在若干入度为0的点

下面就是重点了,只需要收买(也就是计算这个强连通分量中Minimize的Money)所有入度为0的缩点(根结点)就一定可以抓完 全图的 间谍。

假如收买了根点之后无法收买缩点u,那么缩点u一定不是根点的子结点,也就意味着u绝对不和这个DAG联通,那u的入度为0(U肯定也是根结点),就要收买u,所以收买所有根点是可以抓整个DAG的间谍的。

所以,当根点无法被收买的时候,那无解,统计一下无法被收买的强连通分量(也就是根点)之中最小的点,然后输出即可

或者,有解,那么就统计根点的最小花费,加起来就OK。

不需要DFS/BFS。统计的时候可以玩枚举(强连通分量不会太多……)

 

 

One Comment

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据