#3763. 最小环

内存限制:512 MiB 时间限制:10 Sec

题目描述

给定一个无向图,某些点之间连有一条可以双向通过的边,假设结点a,b之间有边,则从a到b会得到c[a][b]个糖果,从b到a会得到c[b][a]个糖果。
问在图中是否存在一个环,可以无限获得糖果(即边权和为正);如果存在,在这些正环中,点数最少的环有多少个点?
对于环的定义:环是一些点的序列,a1,a2,...,ak,a1和a2相连,a2和a3相连,...,ak和a1相连。其中ai和aj可以重合。对于这个环,它的点数视为K。

输入格式

第一行包含两个整数N,M,分别表示点数和边数。
接下来M行,每行i,j,c[i][j],c[j][i],表示i号点和j号点有一条边,从i到j获得c[i][j]个糖果,从j到i获得c[j][i]个糖果。

输出格式

输出只包含一个整数,表示能够无限获得糖果的环中,最少的点数。
如果不存在那样的环,输出0。

样例

样例输入


			
4 4
1 2 -10 3
1 3 1 -10
2 4 -10 -1
3 4 0 -3

样例输出


			
4

数据范围与提示

对于100%的数据,1<=N<=300,0<=M<=N*(N-1)/2,-10000<=c[i][j]<=10000。 数据不存在重边和自环。

此题存在版权,故不再支持提交,保留在此只供大家参考题面! 望见谅!