Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1月前

05/17
21:55
Stoer-Wagner算法

[bzoj 3345] Pku2914 Minimum Cut

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

有一个N(<=500)的无向图,求将这个图断成两个联通块需要删除的边的边权和最小值。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

两个数n,m,然后m个数每行三个数a,b,c,表示a和b这两个点的连系为c (不会重复出现一对a和b,无序)

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

一个数表示最小的联系度和(即无向图最小割)

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

3 3
1 2 1
2 3 1
3 1 2

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

2

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

m<=10000

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

Stoer-Wagner算法模板题

 

[bzoj 3345] Pku2914 Minimum Cut