P2469 [SDOI2010]星际竞速
可以发现，一个点要么是起点，要么从其它点进入，且每个点最多只会进入一次，出去一次。
因此，可以用流量限制每个点被访问一次，用费用计算代价，问题就转化为了最小费用最大流。
P2153 [SDOI2009] 晨跑
题目已经指明了要求最长天数的条件下的最短路，因此可以使用最小费用最大流。
P2805 [NOI2009] 植物大战僵尸
最大权闭合子图。
- \((i,j)\) 向 \((i,j+1)\) 连边。
- 如果 \((i,j)\) 能攻击 \((x,y)\)，\((x,y)\) 向 \((i,j)\) 连边。
可能不是 DAG，因此要把反图拓扑排序不能到的点删掉。
P4843 清理雪道
有源汇上下界最小流。
连边方式：
- \((S,i,0,\infty)\)。
- \((i,T,0,\infty)\)
- \((i,j,1,\infty)\)。
P4043 [AHOI2014/JSOI2014]支线剧情
\(S\) 点即为 \(1\) 号点。
对于原图上的每一条边，连一条流量为 \((1,\infty)\)，费用为边权的边。
对于原图上的每一个点，向 \(T\) 连一条流量为 \((0,\infty)\)，费用为 \(0\) 的边。
然后跑最小费用可行流即可。
P4202 [NOI2008] 奥运物流
设环长为 \(len\)，答案为
\[R(1)=\frac{\sum_{i=1}^{n}k^{d_i}c_i}{1-k^{len}} \]可以发现，修改一定是接到 \(1\) 的下面。
除去环可以直接在树上 dp，设 \(dp(u,m,d)\) 表示 \(u\) 子树内，当 \(u\) 的深度为 \(d\) 且还有 \(m\) 次机会所能得到的最大值。
对于环可以特殊处理，每次枚举环的长度计算贡献，剩下的部分就是一棵树，用如上 dp 计算即可。
标签：infty,图论,原图,费用,省选,09,最小,连边,dp From： https://www.cnblogs.com/yanchengzhi/p/17002013.html