7763: BZOJ3763：最小环

给定一个无向图，某些点之间连有一条可以双向通过的边，假设结点a,b之间有边，则从a到b会得到c[a]个糖果，从b到a会得到c[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。 数据不存在重边和自环。 此题存在版权，故不再支持提交，保留在此只供大家参考题面！ 望见谅！

题目来源

没有写明来源