bzoj#P4773. 负环
负环
题目描述
在忘记考虑负环之后,黎瑟的算法又出错了。对于边带权的有向图 ,请找出一个点数最小的环,使得环上的边权和为负数。保证图中不包含重边和自环。
输入格式
第一行两个整数 ,表示图的点数和边数。
接下来的 行,每行三个整数 ,表示有一条从 到 ,权值为 的有向边。
输出格式
仅一行一个整数,表示点数最小的环上的点数,若图中不存在负环输出 0
。
数据规模与约定
对于 的数据,,,,。
在忘记考虑负环之后,黎瑟的算法又出错了。对于边带权的有向图 G=(V,E),请找出一个点数最小的环,使得环上的边权和为负数。保证图中不包含重边和自环。
第一行两个整数 n,m,表示图的点数和边数。
接下来的 m 行,每行三个整数 ui,vi,wi,表示有一条从 ui 到 vi,权值为 wi 的有向边。
仅一行一个整数,表示点数最小的环上的点数,若图中不存在负环输出 0
。
对于 100% 的数据,2≤n≤300,0≤m≤n×(n−1),1≤ui,vi≤n,∣wi∣≤104。