PDF《NOIP 模拟题》

4 2

4 1

1 0

3 1

1 2

2 3

0 1

2 2

0 2

3 2

1 3

3 3 【样例输出】

1 0 【子任务】 ? 子任务一(4 组数据) :输入数据保证无障碍物,每回合开始玩家都在安全区中;

? 子任务二(4 组数据) :输入数据保证无障碍物,每回合开始玩家不一定在安全 区中,1 ≤ n ≤ 10,1 ≤ m ≤ 20;

? 子任务三(4 组数据) :输入数据保证无障碍物,每回合开始玩家不一定在安全 区中,10 <

n ≤ 400,20 <

m ≤

105 ;

? 子任务四(4 组数据) :输入数据保证有障碍物,1 ≤ n ≤ 10,1 ≤ m ≤ 20;

? 子任务五(4 组数据) :输入数据保证有障碍物,10 <

n ≤ 400,20 <

m ≤

105 . 第8页共12 页NOIP 模拟题 第14 套 贪心算法(greedy) 贪心算法(greedy) 【题目描述】 点独立集是图论中的概念.一个点独立集是一个图中一些两两不相邻的顶点的集 合,亦即一个由顶点组成的集合 S ,使得 S 中任两个顶点之间没有边.顿顿设计了一 个在无向图上求解点独立集的算法,希望你可以帮他实现一下. 算法框架 1. 对于给定的无向图,不断地使用 归约规则 缩减图的规模,直至无法继续使用 为止. 2. 当无法使用归约规则时,每次 贪心 地选取一个顶点直接从图中删去,直至能 继续使用归约规则或图为空. 3. 反复迭代上述步骤,直至图为空. 归约规则 每成功地执行一次规约规则,会将一个顶点选入答案中,选入的顶点按下面的规则 唯一确定: 1. 若图中有顶点度为 0,则将其中编号最小的选入答案中,并把它从图中删去;

2. 否则若图中有顶点度为 1,则将其中编号最小的选入答案中,并把它和它唯一的 邻接顶点从图中删去;

3. 否则不能成功执行规约规则. 贪心策略 当图中不存在度小于

2 的顶点时,需要从图中贪心地删去一........