bzoj#P4773. 负环

负环

题目描述

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

输入格式

第一行两个整数 n,mn,m,表示图的点数和边数。
接下来的 mm 行,每行三个整数 ui,vi,wiu_i,v_i,w_i,表示有一条从 uiu_iviv_i,权值为 wiw_i 的有向边。

输出格式

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

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

数据规模与约定

对于 100%100\% 的数据,2n3002 \le n \le 3000mn×(n1)0 \le m \le n\times (n-1)1ui,vin1 \le u_i,v_i\le nwi104|w_i| \le 10^4