TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3611
  • 题目
  • P3611【CQOI2016 Day1】不同的最小割
    限制 : 时间限制 : 20000 MS   空间限制 : 524288 KB
    问题描述

            学过图论的同学都知道最小割的概念:对于一个图,某个对图中节点的划分将图中所有节点分成两部分,如果节点s,t不在同一个部分中,则称这个划分是关于s,t的割。对于带权图来说,将所有顶点处在不同部分的权值相加所得到的定义为这个歌的容量,而s,t的最小割指的是在关于s,t的个中容量最小的割。
            而对冲刺NOI竞赛的选手而言,求带权图中两点的最小割已经不是什么难事。我们可以把视野放宽,考虑有N个点的五项连通图中所有点对的最小割容量,共能得到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

    提示

    数据范围:
            对于50%的数据,N≤200,M≤2000;
            对于100%的数据,1≤N≤850,1≤M≤8500,1≤w≤100000


    来源  感谢nodgd仔细修改原版题目描述中的错别字