对于题目给的图\(G\)，我们添加一条边\((t,s)\)转化成\(G_1\)，对\(G_1\)求无源汇上下界可行流，添加虚拟源汇点\(S,T\)得到的图是\(G_2\)，对\(G_2\)跑dinic，此时得到的最大流\(f\)满足\(S\)的每条出边都是满的，\(T\)的每条入边都是满的，\(f\)诱导出的\(G_2\)的残存网络为\(G_3\)，在\(G_3\)中将\(s,t\)分别当做源点和汇点跑dinic，此时跑出来的增广路一定不包含\((t,s),S,T\)（因为增广路是简单路径，所以不包含\((t,s)\)；因为\(G_3\)中\(S\)只有入边所以一旦进入\(S\)就出不去了，所以不包含\(S\)；因为\(G_3\)中\(T\)只有出边所以无法进入\(T\)，所以不包含\(T\)），设这个dinic结束之后，得到一条最大流\(f_1\)，此时\(s,t\)流量不守恒，将\(f\)与\(f_1\)相加，并令\(G_2\)中\((t,s)\)的权值为\(f_1\)，此时不难验证仍然得到了\(G_2\)的一个最大流，而\(G_2\)的一个最大流就可以转换为\(G_1\)的一个可行流
标签：最大,包含,有源,汇点,下界,dinic,汇上 From： https://www.cnblogs.com/dingxingdi/p/18394367