最小割树是指构造一颗树，使得任意\(u,v\)的最小割等于树上两点之间的最小边权，且\(u,v\)的割边方案就是这条边两端割边方案。这里我们不考虑方案相同，只要求答案相同，这个叫等价流树。构造：选取任意两点\(u,v\)，连\((u,v,f(u,v))\)的边。则整个点集被分为两个联通块\(S\)

本文是在作者阅读多篇博客后糅合而成的，部分内容有雷同。最小割树又称Gomory-Hu树，由RalphEdwardGomory和TeChiangHu于1961年发表的论文中共同提出。最小割树可以在\(n−1\)次最大流中构建，并通过树上RMQ求任意两点之间的最小割。板子题：P4897【模板】最小割树（G

P4897【模板】最小割树（Gomory-HuTree）题意：求任意两个点的最小割。首先任取两个点\(s,t\)，算出这两个点的最小割，然后将这两个点连上权值为\(w\)的边。求最小割的过程中，图被分为了两个联通块。在这两个联通块中递归执行上述过程，就能建成最小割树。任意两个点的最小割，就是它们

最小割树（Gomory-HuTree）是一种可以在\(O(Vf)\)的时间里求出一个图中全源最小割的算法，其中\(f\)为一次最大流的时间。记原图为\(G=(V,E)\)，其最小割树为\(G'=(V,E')\).在最小割树中，任两点间的最小割等于它们在原图中的最小割，且\(\forall(u,v)\inE'\)，\(E'\setminus\{u

问题描述给定一张图，求任意两点的最小割。要求跑\(n\)次最大流。做法暴力需要跑\(n^2\)次最大流，然而这样很浪费，因为求出\(u,v\)两点的最小割以后，我们还获得了至少一种最小割方案，可以通过这一方案获得更多信息。注意到假设通过最小割断开后，\(s,t\)所在集合分别为\(S,T