题目描述

给定一个无向图，某些点之间连有一条可以双向通过的边，假设结点 $a,b$ 之间有边，则从 $a$ 到 $b$ 会得到 $c_{a,b}$ 个糖果，从 $b$ 到 $a$ 会得到 $c_{b,a}$ 个糖果。

问在图中是否存在一个环，可以无限获得糖果（即边权和为正）；如果存在，在这些正环中，点数最少的环有多少个点？

对于环的定义：环是一些点的序列，$a_1,a_2,\dots,a_k$，$a_1$ 和 $a_2$ 相连，$a_2$ 和$a_3$ 相连，$\dots$， $a_k$ 和 $a_1$ 相连。其中 $a_i$ 和 $a_j$ 可以重合。对于这个环，它的点数视为 $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 \le n \le 300$，$0 \le m \le \frac{n \times (n-1)}{2}$，$-10^4 \le c_{i,j} \le 10^4$。数据不存在重边和自环。

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