8773: BZOJ4773:负环

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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


输入格式

第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


输出格式

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


样例输入

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

样例输出

2

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: