#2042. 「CQOI2016」不同的最小割

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

学过图论的同学都知道最小割的概念:对于一个图,某个对图中结点的划分将图中所有结点分成两个部分,如果结点 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