题意就是给定一个竞赛图，多次询问，每次询问有多个源点 \(s_1,s_2,\cdots s_k\)，单个汇点 \(t\)，一条边流量为 \(1\)，求最大流。
考虑转成最小割，相当于将 \(V\) 划分成两个集合 \(S,T\)，\(S\cup T=V\) 且 \(S\cap T=\varnothing\)，\(s_i\in S,t\in T\)，然后令 \(f(S,T)=\sum\limits_{u\in S}\sum\limits_{v\in T}[(u,v)\in E]\) 最小。
考虑竞赛图的性质，每两个点之间都有连边，所以：
\[\begin{aligned}f(S,T)+f(T,S)&=\sum\limits_{u\in S}\sum\limits_{v\in T}[(u,v)\in E]+[(v,u)\in E]\\&=|S|\cdot |T|\end{aligned} \]然后再推 \(f(S,T)-f(T,S)\)：
\[\begin{aligned}f(S,T)-f(T,S)&=\sum\limits_{u\in S}\sum\limits_{v\in T}[(u,v)\in E]-[(v,u)\in E]\\&=\sum\limits_{u\in S}\left(\sum\limits_{v\in V}[(u,v)\in E]-\sum\limits_{v\in S}[(u,v)\in E]-\sum\limits_{v\in V}[(v,u)\in E]+\sum\limits_{v\in S}[(v,u)\in E]\right)\\&=\sum\limits_{u\in S}\left(\sum\limits_{v\in V}[(u,v)\in E]-[(v,u)\in E]\right)\\&=\sum\limits_{u\in S}out_u-in_u\end{aligned} \]其中 \(out_u\) 表示 \(u\) 的出度，\(in_u\) 表示 \(u\) 的入度。第二行推第三行是因为考虑一条边的贡献，那么 \(S\) 的导出子图的所有点出入度之差的和显然为 \(0\)。
于是能够得到：
\[f(S,T)=\frac{|S|\cdot |T|+\sum\limits_{u\in S}out_u-in_u}{2} \]由于 \(T=V\setminus S\)：
\[f(S,T)=\frac{|S|(n-|S|)+\sum\limits_{u\in S}out_u-in_u}{2} \]考虑 \(|S|\) 相同时，只需要最小化 \(\sum\limits_{u\in S}out_u-in_u\)，那么考虑 \(|S|\) 从小到大的过程，直接按照 \(out_u-in_u\) 从小到大排序然后一个个加入集合 \(S\) 即可。
注意到 \(s_i(1\le i\le k)\in S\) 且强制 \(t\notin S\)。
复杂度 \(O(n(n+m))\)。
标签：right,limits,P9545,2023,考虑,aligned,sum,road,out From： https://www.cnblogs.com/Ender32k/p/17715910.html