4897

P4897 【模板】最小割树(Gomory-Hu Tree)

题意 给定一张图,\(q\) 次询问,每次询问两点的最小割。 Sol 最小割树模板题。 考虑去分治一个集合 \(S\)。 每次在里面随便找两个点作为源点和汇点,然后在原图上跑最小割。 然后在残量网络上标记源点集和汇点集。 分别放到两个不同的集合,然后继续分治下去即可。 Code namespace ......
Gomory-Hu 模板 Gomory P4897 4897
共1篇  :1/1页 首页上一页1下一页尾页