都是大水题 很多题都是口胡 而且题解写的并不好...[SCOI2007] 蜥蜴把一个点拆成两个点 中间连上点权的边 luoguP2711 小行星可以分成三个部, x 部, y 部与 z 部, 做最小割 x 与 s 相连, w=1;z 与 t 相连, w=1, 以 y 部为中间部连接 x 与 z w=infy 部的点要拆点 连 w=1 边 luoguP3410 拍照最大权闭合子图建图: 如果选 A 则必须选 B 则 A 向 B 连 \(\infty\) 边选 A 收益为正 则 S 向 A 连此收益的边 否则向 T 连边最终答案等于所有物品正收益之和减最小割这道题直接按题意连边就行 [SDOI2010] 星际竞速基本复制 George1123 题解想象有 \(n+1\) 个人接力跑 , 分别在点 \(s\) 和 \(1\sim n\) 上 , 开始时接力棒在 \(s\) 那个人手上. 这时候他拿着接力棒开始跑, 到达某个星球后停止, 把接力棒交给该星球上的选手, 并打卡结束比赛. 该选手又出发, 循环此过程. 每个星球只可以打卡一次, 必须打卡. 路上走过的路程相当于费用. 最后的最大流最小费用就是答案, 而原问题与此等效. 建图: 每个点拆成左右两边的点 s 向左侧点流量 1 费用 0(相当于等待的人)s 向右侧点流量 1 费用 \(a_i\) 右侧点向 t 流量 1 费用 0 左边向右边连原图的边注意只有 DAG 该建图才能成立这种模型大概是右边点用于打卡保证所有点被经过恰好一次 左边用于出发 [JLOI2010] 冠军调查 S 连向同意的人, T 连向不同意的人, 朋友之间连 w=1 双向边当 S 和 T 还连通时则必然存在一条路径, 证明有人产生矛盾直接最小割 [SDOI2013] 费用流所有的单位费用应该被分配在流量最大的边上二分 判断是否存在最大流 会有实数流量 (不过不是很清楚网络流跑实数流量复杂度会怎样) 狼抓兔子看这个我是一点平面图的常识都没有这个实现应该简单一点
来源: http://www.bubuko.com/infodetail-3625482.html