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

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

@krydom4月前

04/6
08:58
倍增 矩阵乘法

[bzoj 4773] 负环

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

在忘记考虑负环之后,黎瑟的算法又出错了。对于边带权的有向图 G = (V, E),请找出一个点数最小的环,使得环上的边权和为负数。保证图中不包含重边和自环。

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

第1两个整数n, m,表示图的点数和边数。
接下来的m行,每<=三个整数ui, vi, wi,表<=有一条从ui到vi,权值为wi的有向边。
2 <= n <= 300
0 <= m <= n(n <= 1)
1 <= ui, vi <= n
|wi| <= 10^4

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

仅一行一个整数,表示点数最小的环上的点数,若图中不存在负环输出0。

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

3 6
1 2 -2
2 1 1
2 3 -10
3 2 10
3 1 -10
1 3 10

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

2

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

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

先倍增出到2^k之后有负环的k,然后像求lca一样做回去就可以了

 

[bzoj 4773] 负环