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

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

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit][Status][Web Board][Creator:]

Description

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

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

输入格式

输入文件第一行包含两个数 N,MN, MN,M,表示点数和边数。
接下来 MMM 行,每行三个数 u,v,wu, v, wu,v,w,表示点 uuu 和点 vvv(从 111 开始标号)之间有一条权值是 www 的边。

输出格式

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

样例

样例输入

4 4
1 2 3
1 3 6
2 4 5
3 4 4

样例输出

3

数据范围与提示

Case # NNN MMM
1 252525 150150150
2 505050 500500500
3 100100100 100010001000
4 150150150 150015001500
5 200200200 200020002000
6 300300300 300030003000
7 400400400 400040004000
8 500500500 500050005000
9 700700700 700070007000
10 850850850 850085008500

对于所有测试点,w≤100000w \leq 100000w100000

Source

 

[Submit][Status]