Browse Tag

图论

POJ 3469:Dual Core CPU (最大流)

有n个模块,每个模块在A上花费ai,在B上花费bi,然后有m个任务(ai,bi,wi),如果ai,bi不在一起工作的话需要额外花费wi,求最小花费。

『图论』有向图强连通分量的 Tarjan 算法

  Tarjan算法是基于对图深度优先搜索的算法,每个强连通分量为搜索树中的一棵子树。

  搜索时,把当前搜索树中未处理的节点加入一个堆栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。