今天又遇到这个题了，我竟然忘记了，真不应该啊。重温一下，把文章从qq空间转过来吧。

说下这题大概思路吧！

1.把有限制的点去掉，剩下的找出各个连通分量，prim最小生成树，就是一片森林。

2.每个连通分量找最短的一条边连到有限制的那点，得到最小m度限制生成树

3.由最小m度限制生成树，得到最小m+1度，m+2度……一直到k度最小限制生成树.

阅读剩余部分 >>

给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。

求二分图最大匹配可以用最大流(Maximal Flow)或者匈牙利算法(Hungarian Algorithm)

这里做的题目是poj3041，把算法都弄懂了之后，发现它真的很水。

阅读剩余部分 >>

在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。

这里使用的是tarjan的算法，具体可以参考： http://www.cppblog.com/sosi/archive/2010/09/26/127797.aspx

阅读剩余部分 >>