TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Course  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3611
  • Problem
  • P3611【CQOI2016 Day1】不同的最小割
    Limits : Time Limit : 20000 MS   Memory Limit : 524288 KB
    Description

            学过图论的同学都知道最小割的概念:对于一个图,某个对图中节点的划分将图中所有节点分成两部分,如果节点s,t不在同一个部分中,则称这个划分是关于s,t的割。对于带权图来说,将所有顶点处在不同部分的权值相加所得到的定义为这个歌的容量,而s,t的最小割指的是在关于s,t的个中容量最小的割。
            而对冲刺NOI竞赛的选手而言,求带权图中两点的最小割已经不是什么难事。我们可以把视野放宽,考虑有N个点的无向连通图中所有点对的最小割容量,共能得到N(N-1)/2个数值。这些数值中互不相同的有多少个呢?这似乎是一个有趣的问题。

    Input Format

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

    Output Format

            输出文件第一行为一个整数,表示个数。

    Sample Input

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

    Sample Output

    3

    Hint

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


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