跳到主要内容
图灵 OJTURING / ONLINE JUDGE

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

  • ID: 162
  • 传统题
  • 1000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:待分级
  • 上传者:
  • 网络流
  • 图论
  • 难度待定
  • 难度
  • 共享题库
  • LibreOJ
  • 中文题面
  • 题目来源
  • 题面语言

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

题目描述

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

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

输入格式

输入文件第一行包含两个数 ,表示点数和边数。
接下来 行,每行三个数 ,表示点 和点 (从 开始标号)之间有一条权值是 的边。

输出格式

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

样例

样例输入

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

样例输出

3

数据范围与提示

Case #
1
2
3
4
5
6
7
8
9
10

对于所有测试点,。


题目来源:fps-loj-small-pics.zip;FPS 共享题包,题包内第 39 题。保留原作者与原赛事署名。