#P4435. [Cerc2015]Juice Junctions

    ID: 3640 传统题 1000ms 512MiB 尝试: 315 已通过: 92 难度: 8 上传者: 标签>CF2400提高+/省选-Gomory–Hu 树Edmonds–Karp最大流最小割定理普通并查集贡献法桶排序

[Cerc2015]Juice Junctions

题目描述

你被雇佣升级一个旧果汁加工厂的橙汁运输系统。系统有管道和节点构成。每条管道都是双向的,且每条管道的流量都是 11 升每秒。管道可能连接节点,每个节点最多可以连接 33 条管道。节点的流量是无限的。节点用整数 11 到 nn 来表示。在升级系统之前,你需要对现有系统进行分析。对于两个不同节点 ss 和 tt,s−ts - t 的流量被定义为:当 ss 为源点,tt 为汇点,从 ss 能流向 tt 的最大流量。以下面的第一组样例数据为例,1∼61 \sim 6 的流量为 33,1∼21 \sim 2 的流量为 22。计算每一对满足 a<ba \lt b 的节点 a∼ba \sim b 的流量的和。

输入格式

第一行包括 22 个整数 nn 和 mm,表示节点数和管道数。

接下来 mm 行,每行包括两个相异整数 a,ba,b,表示一条管道连接节点 a,ba,b。

每个节点最多连接 33 条管道,每对节点最多被一条管道连接。

输出格式

输出一个整数——每对满足 a<ba \lt b 的节点 a∼ba \sim b 的流量之和。

6 8
1 3
2 3
4 1
5 6
2 6
5 1
6 4
5 3
36

数据范围

对于 100%100 \% 的数据,2≤n≤30002 \le n \le 3000,0≤m≤45000 \le m \le 4500,1≤a,b≤n1 \le a, b \le n。