一开始看这个题以为是bfs找最近两个栅栏并相连,不过好像时间复杂度还是有点高。最小割做法实在是优秀。 题目描述 “狼爱上羊啊爱的疯狂,谁让他们真爱了一场;狼爱上羊啊并不荒唐,...
网络流
洛谷 P1361 小M的作物 题解【网络流】【最小割】
最小割建模真的是毒瘤啊。。。 题目描述 小M在MC里开辟了两块巨大的耕地A和B(你可以认为容量是无穷),现在,小P有n中作物的种子,每种作物的种子有1个(就是可以种一棵作物)(用1...
洛谷 P3705 [SDOI2017]新生舞会 题解【网络流】【分数规划】
这个题是主要是考01分数规划和网络流建模。 题目描述 学校组织了一次新生舞会,Cathy作为经验丰富的老学姐,负责为同学们安排舞伴。 有n个男生和n个女生参加舞会,每一个男生和一个女生一起跳舞...
洛谷 P1343 地震逃生 题解【网络流】【最大流】
考试时间 2018/5/20 题目描述 汶川地震发生时,四川**中学正在上课,一看地震发生,老师们立刻带领x名学生逃跑,整个学校可以抽象地看成一个有向图,图中有n个点,m条边。1号点为教室,n号点为安全地带,每条...