现在已知如下问题，并告诉你这题可以用网络流来解决，你该怎么做，该怎么建出网络流的模型？一些前提：显然可以发现绝不可能走横向向左的边，但可能走竖向向上的边（如下图）那么图其实就是这样的：问从\(s\)到\(t\)的最小花费如果没有那\(m\)条限制，我们直接跑最短路就行了，加上这些限制

2024-04-06太空飞行计划问题最小割模型源点向实验连边，容量是收益仪器向汇点连边，容量是花费割掉一条边，代表放弃实验/购买仪器合法的情况就是源点汇点不连通，代表要么买了仪器，要么用到这台仪器的所有实验都放弃记录总收益为sum，最小割为res\(ans=sum-res\)（这题读入特别恶心

题面给定一张含\(n\)个点，\(nk\)条边的图\(G=(V,E)\)，判断是否满足\(\forallX\subsetneqqV,X\neq\varnothing\)，\(X\)导出子图的边数\(\div\)\(|X|\)\(<k\)。\(nk\le5\times10^4\)。题解首先要发现这是一个最大权闭合子图的问题，对于一条边\((x,y)\)，其贡献为\(

一道一道记太浪费文章篇数了。先记几种dinic的复杂度。一般网络：\(O(n^2m)\)各边容量为\(1\)的网络：\(O(m\min\{m^{\frac{1}{2}},n^{\frac{2}{3}}\})\)二分图：\(O(m\sqrtn)\)更详细的分析。最大流UVA10735混合图的欧拉回路存在欧拉回路的判断条件：每个点出度=入度