【BZOJ 4519】不同的最小割(分治最小割)

Description

给定一个无向连通图,问两两点之间的最小割的大小有多少种。

$n\leq 850,m\leq 8500$

题目解析

【复习】这是一道分治最小割板题。

对于第一个联通点集,随意一个点对,用他的最小割将整个点集割成两半,递归处理。

这样会形成一颗二叉树,每个点表示点集,边表示割,两两点之间的最小割就等于树上路径的最小值。

这道题就只用记录有多少种不同的边权了。

代码

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注