BZPRO
#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。
数据不存在重边和自环。
此题存在版权，故不再支持提交，保留在此只供大家参考题面！ 望见谅！
BZPRO