强连通专题

按着风神大大的博客切啊切~
提示在每道题后面,选中即可显示
HDOJ
hdoj1269 迷宫城堡 判断是否是一个强连通★
hdoj2767Proving Equivalences 至少加几条边让整个图变成强连通★
hdoj3836 Equivalent Sets 至少加几条边让整个图变成强连通★
hdoj1827 Summer Holiday 传递的最小费用★★
hdoj3072 Intelligence System 传递的最小费用★★
hdoj3861The King’s Problem 强连通+二分匹配★★

这题必须好好记下,题意木有读懂,orz。。
题意:在有向图G中,相互可达的两个点必须划分在一个区,并且一个区里的任意两个点,至少存在一条单向路径(不经过其他区的点)。问原图最少需要划分成几个区。
思路:首先相互可达的点必须在一个区,那么强连通缩点,这样形成了一个DAG森林。问题转化为:给定一个DAG森林,最少用几条路径可以覆盖所有点,每个点只能属于一条路径。其实就是求DAG森林的最小路径覆盖,拆点转化成二分图,最小路径覆盖=原图顶点-最大匹配
通过这道题顺便学了最小路径覆盖,然后整理了一些覆盖集、独立集之间的关系,爽。
代码(匹配还没学,,用sap跑的。。囧~)