#洛谷 通往奥格瑞玛的道路

题面对我来说貌似有毒,看了很长时间才看懂这是一个最大值最小问题 果断二分答案。

主要思想是先跑一边Bellman-Ford+队列优化(也叫SPFA)把二分值设定成+∞ 然后看一看如果到终点的花费大于血量就输出AFK(away from keyboard)

如果可行就快排点权+二分下标 如果当前二分值可以跑到终点(跑SPFA判)就向左找(升序sort),不然就向右找。

跑SPFA的时候传一个upat也就是二分值 把点权大于二分值的点都判(删)掉 

 

还有一点就是最后还要判一下二分值。链式前向星+SPFA+手写Sort,没有注释……

 

 

 

CodeVS&Luogu 间谍网络

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

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

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

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

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

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

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

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