假设给定一个无向、无权图 G= (V, E) 和一些成本函数 c:E→R>0，为每条边 e∈E 分配一个正成本 c(e)。目标是计算最小成本的 G 的最小割（即，由最少边数组成的割中的最小成本割）。给出一个算法，它很有可能在多项式时间内找到这样一个最小成本最小割。你的算法的运行时间是多少？提示：Karger 算法
方法 I：做 Karger n^c 次（仍然是多项式，在 c 的 n 上提高指数）并比较得到的最小切割。c >=1
方法二：当 Karger 处于收缩边缘时，提高高权重的概率。不影响运行时间
甚至两者兼而有之？
方法 我似乎没有向 Karger 算法添加任何内容。从这篇文章的介绍：“通过迭代这个基本算法足够的次数，可以高概率找到最小割。” 换句话说，方法 I 已经是算法的一部分。
方法 II 在技术上是不必要的（无论如何，Karger 的算法最终都会找到最小割），并且可能会严重损害算法。例如，考虑一个可以通过删除一条特定边来切割的图，但需要两条或更多条边进行切割（数字代表一条边的成本）：
如果该特定边的成本最高（本例中为 999），则提高选择该边进行收缩的概率会降低找到（最小成本）最小割的概率。事实上，它降低了找到（任何成本）最小割的概率。
所以你需要做的就是运行标准算法。在每次迭代中，您需要检查新找到的切口是否比当前最佳切口的边缘更少。如果是这样，则新找到的剪辑是最好的剪辑（到目前为止）。如果新找到的切割与当前最佳切割具有相同数量的边，则比较成本以查看哪个更好。