P4123 [CQOI2016]不同的最小割

    • 296通过
    • 618提交
  • 题目提供者 goodbye2018
  • 评测方式 云端评测
  • 标签 分治 最小割 网络流 各省省选 2016 重庆
  • 难度 省选/NOI-
  • 时空限制 3000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    推荐的相关题目 显示

    题目描述

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

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

    输入输出格式

    输入格式:

    第一行包含两个数 $N,M$,表示点数和边数。

    接下来 $M$ 行,每行三个数 $u,v,w$,表示点 $u$ 和点 $v$ (从 $1$ 开始标号) 之间有一条权值是 $w$ 的边。

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    4 4
    1 2 3
    1 3 6
    2 4 5
    3 4 4
    输出样例#1: 复制
    3

    说明

    $1\leq N\leq 850,1\leq M\leq 8500,1\leq w\leq 100000$。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。