#PQJ2674x15778. QOJ 2674_15778

    ID: 2849 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:CQTSC 2016网络流并查集

QOJ 2674_15778

学过图论的同学都知道最小割的概念:对于一个图,某个对图中结点的划分将图中所有结点分成两个部分,如果结点 𝑠 , 𝑡 不在同一个部分中,则称这个划分是关于 𝑠 , 𝑡 的割。对于带权图来说,将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量,而 𝑠 , 𝑡 的最小割指的是在关于 𝑠 , 𝑡 的割中容量最小的割。

而对冲刺 NOI 竞赛的选手而言,求带权图中两点的最小割已经不是什么难事了。我们可以把视野放宽,考虑有 𝑁 个点的无向连通图中所有点对的最小割的容量,共能得到 𝑁 ( 𝑁 − 1 ) 2 个数值。这些数值中互不相同的有多少个呢?这似乎是个有趣的问题。

输入格式

输入文件第一行包含两个数 𝑁 , 𝑀 ,表示点数和边数。

接下来 𝑀 行,每行三个数 𝑢 , 𝑣 , 𝑤 ,表示点 𝑢 和点 𝑣 (从 1 开始标号)之间有一条权值是 𝑤 的边。

输出格式

输出文件第一行为一个整数,表示不同的最小割容量的个数。

样例数据 样例 1 输入 4 4 1 2 3 1 3 6 2 4 5 3 4 4 样例 1 输出 3 子任务 Case # 𝑁

𝑀

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

对于所有测试点, 𝑤 ≤ 100000 。