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混合图的欧拉回路存在欧拉回路的判断条件：每个点出度=入度