缩点不只用于转化图为 DAG,还可以进一步发掘图的性质,从而将题目变成结论题所求信息转化到图上,方便建模。
P2002
https://www.luogu.com.cn/problem/P2002
在一个强连通分量里面的城市是绝对可以互相到达的,所以我们缩点。然后在新图中,我们只需要给入度为 \(0\) 的点发送信息,整张图都可以走完了。但其实我们并不需要建新图,只需要知道图中新点的入度,也就是找到新图中需要建哪些边。如果原图中一条边连接的两个端点在同一个强连通分量里面,那么这条边就不是新图里的边,防止窝里斗;反之,如果 \(scc_u \ne scc_v\),则 \(u \rightarrow v\)是新图里的边,这时候 \(in_{scc_v}\) 自加。最后统计 \(in_u=0\) 的点数。
P1262
https://www.luogu.com.cn/problem/P1262
把间谍 \(u\) 可以揭发 \(v\) 当作连边 \(u \rightarrow v\),这样可以发现,在一个强连通分量内,只要有一个间谍被收买,其他的间谍都寄了。所以我们缩点,点权取强连通分量内最低的收买费用,所有点权加起来就可以了。那么什么时候无解呢?当有一个强连通分量的点权为 \(inf\) 也就是说这个强连通分量里面的间谍都不可以被金钱收买,这时候我们输出这个强连通分量里面编号最小的间谍即可。
P2341
https://www.luogu.com.cn/problem/P2341
受欢迎的奶牛是被所有牛喜爱,如果我们将 \(u\) 喜欢 \(v\) 转化为 \(u \rightarrow v\) 有一条有向边,那么受欢迎的牛就是所有其他的奶牛都可以到达的牛。缩点后,每个强连通分量记录其大小 \(siz\),如果新图内只有一个出度为 \(0\) 的点,那么所有其他点内奶牛都可以到达这个出度为 \(0\) 的点,这个强连通分量里面的牛都是受欢迎的奶牛。但是如果缩完后有多个出度为 \(0\) 的点,那么这些出度为 \(0\) 的点都不可以互相到达,所以就没有受欢迎的牛了。
P1407
https://www.luogu.com.cn/problem/P1407
男女结婚关系,然后题目中说男男女女不可以结婚(完全错误的,彻底错误的,毫不讲理的,固执己见的,墨守成规的,老套过时的),所以这很像一个二分图匹配问题。\(u\) 和 \(v\) 现在是夫妻,连边 \(u \rightarrow v\),题目中相当于给了我们一个完美匹配,如果我们拆散 \(u\) 和 \(v\),其他的不变,如果可以从 \(u\) 出发再找到一条增广路,就说明这对夫妻关系是不稳定的,反之亦然。
当然,对于缩点的做法,我们可以一样地建边,在一个强连通分量里面的夫妻是不稳定的,反之亦然,所以缩点后判断 \(scc_u\) 和 \(scc_v\) 就可以了。
P2746(P2812)
严谨的结论题。子任务 A 相当于 P2002,缩点后统计入度为 \(0\) 的点数即可。
子任务 B 就是问我们把新图变为一个环需要添加的最少边数。https://www.luogu.com.cn/blog/Ametsuji-tachiaki/solution-p2746 这篇文章对我启发很大,分类讨论:如果一个点有入度也有出度,那是怎么放都可以到达的;那如果没有入度或出度,我们将这些点首尾相连,合成二星卡,技能翻倍,由无出度点连向无入度点,当然每一个无入度或出度点都要被连,这样新图就是一个环了。所以答案为入度为 \(0\) 的点数和出度为 \(0\) 的点数的最大值。