4071: 「CQOI2016」不同的最小割
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
学过图论的同学都知道最小割的概念：对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点 $s, t$ 不在同一个部分中，则称这个划分是关于 $s, t$ 的割。对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而 $s, t$ 的最小割指的是在关于 $s, t$ 的割中容量最小的割。
而对冲刺 NOI 竞赛的选手而言，求带权图中两点的最小割已经不是什么难事了。我们可以把视野放宽，考虑有 $N$ 个点的无向连通图中所有点对的最小割的容量，共能得到 $\frac {N(N−1)} {2}$ 个数值。这些数值中互不相同的有多少个呢？这似乎是个有趣的问题。
输入
输入文件第一行包含两个数 $N, M$，表示点数和边数。
接下来 $M$ 行，每行三个数 $u, v, w$，表示点 $u$ 和点 $v$（从 $1$ 开始标号）之间有一条权值是 $w$ 的边。
输出
输出文件第一行为一个整数，表示不同的最小割容量的个数。
样例输入 复制
4 4
1 2 3
1 3 6
2 4 5
3 4 4样例输出 复制
3提示
数据范围：| Case # | $N$ | $M$ | |:---:|:---:|:---:| | 1 | $25$ | $150$ | | 2 | $50$ | $500$ | | 3 | $100$ | $1000$ | | 4 | $150$ | $1500$ | | 5 | $200$ | $2000$ | | 6 | $300$ | $3000$ | | 7 | $400$ | $4000$ | | 8 | $500$ | $5000$ | | 9 | $700$ | $7000$ | | 10 | $850$ | $8500$ | 对于所有测试点，$w \leq 100000$。