图论

狼抓兔子

题目描述

现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓兔子还是比较在行的,而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形:   左上角点为(1,1),右下角点为(N,M)(上图中N=3,M=4).有以下三种类型的道路 1:(x,y)<==>(x+1,y) 2:(x,y)<==>(x,y+1) 3:(x,y)<==>(x+1,y+1) 道路上的权值表示这条路上最多能够通过的兔子数,道路是无向的. 左上角和右下角为兔子的两个窝,开始时所有的兔子都聚集在左上角(1,1)的窝里,现在它们要跑到右下角(N,M)的窝中去,狼王开始伏击这些兔子.当然为了保险起见,如果一条道路上最多通过的兔子数为K,狼王需要安排同样数量的K只狼,才能完全封锁这条道路,你需要帮助狼王安排一个伏击方案,使得在将兔子一网打尽的前提下,参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦。 (更多…)

DefFrancis
图论

[ZJOI2009]假期的宿舍

P2055 [ZJOI2009]假期的宿舍

题目描述

学校放假了 · · · · · · 有些同学回家了,而有些同学则有以前的好朋友来探访,那么住宿就是一个问题。比如 A 和 B 都是学校的学生,A 要回家,而 C 来看B,C 与 A 不认识。我们假设每个人只能睡和自己直接认识的人的床。那么一个解决方案就是 B 睡 A 的床而 C 睡 B 的床。而实际情况可能非常复杂,有的人可能认识好多在校学生,在校学生之间也不一定都互相认识。我们已知一共有 n 个人,并且知道其中每个人是不是本校学生,也知道每个本校学生是否回家。问是否存在一个方案使得所有不回家的本校学生和来看他们的其他人都有地方住。 (更多…)

DefFrancis
数据结构

[NOI2016]区间

P1712 [NOI2016]区间

题目描述

在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间,使得这 m个区间共同包含至少一个位置。换句话说,就是使得存在一个 x,使得对于每一个被选中的区间 [li,ri],都有 li≤x≤ri。 对于一个合法的选取方案,它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li,即等于它的右端点的值减去左端点的值。 求所有合法方案中最小的花费。如果不存在合法的方案,输出 −1。 (更多…)

DefFrancis
题解

小Z的游戏分队

P2175 小Z的游戏分队

题目描述

小Z受不了寂寞,准备举办一次DOTA比赛,为了能让ACM班全部都参加比赛,他还特制了一张DOTA地图能够支持任意多人打任意多人。 现在问题来了,怎么把这么多人分成两队?小Z的想法是,每个人报上自己愿意同队的同学,接着小Z会按如下要求将所有人分为两队: 对任意同学甲,和同学甲同队的人,必须都是同学甲愿意同队的同学。 小Z希望两队的人数差尽量小,如果这种分组不存在,那么输出No solution。 (更多…)

DefFrancis
图论

飞行员配对方案问题

P2756 飞行员配对方案问题

题目描述

英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员,其中1 名是英国飞行员,另1名是外籍飞行员。在众多的飞行员中,每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况,试设计一个算法找出最佳飞行员配对方案,使皇家空军一次能派出最多的飞机。 对于给定的外籍飞行员与英国飞行员的配合情况,编程找出一个最佳飞行员配对方案,使皇家空军一次能派出最多的飞机。 (更多…)

DefFrancis