ACM选讲-拓扑排序 ACM选讲-最短路径 ACM 1094 ACM 1178 All possi ■题目描述 题目描述 己知A<B,A<C,B<CC<D,B<DA<B 1)8×8的棋盘上有一个国王 和若干个骑士,他们要集合到 则ABC,D的大小关系,可由前几个表达式确 ■2)可能的移动如右图,允许 ■利用边集数组存储图 多个人位于同一格 of a knight ■3)因王可以骑在骑士的马上 ■还需要记录那些信息? 起移动(亦可换马) 4)计算总移动步数的最小值 图论习题课 ACM选讲-最短路径 ACM选讲-最短路径 解题思路 All possible movements of the king )由Foyd算法可以求得国王和每个 骑士到矩阵中的所有方格的最小步 假设国王和骑士最终都移动 到方格工则最小步数为国王 和每个骑士移动到方格I所 2)Min【每个方格i 需要的步数 国王酶的最小步数 +每个骑士到的最小步数 格工求将国主和个骑上+, 到它的最短距离之和 图论习题课 图论习题课 ACM选讲-最短路径 ACM选讲-最短路径 ACM 1158 (B,2,16,99 P,6,32,13) 题目描述: 题目描述 1) ■城市有若干条街道,每个街道的两端有信号 灯,每个信号灯都有两种颜色。当街道两端 的信号灯颜色一致时,道路才通。已知条件 为街道和每个信号灯初始颜色,以及颜色改 变的颜率。求给定两端点的最小行车时间? (P,2,87,4) 求1到4的最短行车时间 图论习题课 图论习题课4 图论习题课 ACM选讲-拓扑排序 ACM 1094 „ 题目描述： „ 已知A<B, A<C, B<C, C<D, B<D,A<B „ 则A, B, C, D的大小关系，可由前几个表达式确 定？ „ 利用边集数组存储图 „ 还需要记录那些信息？ 图论习题课 ACM选讲-最短路径 ACM 1178 „ 题目描述： „ 1）8×8的棋盘上有一个国王 和若干个骑士，他们要集合到 一点。 „ 2）可能的移动如右图，允许 多个人位于同一格。 „ 3）国王可以骑在骑士的马上 一起移动（亦可换马）。 „ 4）计算总移动步数的最小值 图论习题课 ACM选讲-最短路径 „ 解题思路： „ 假设国王和骑士最终都移动 到方格I,则最小步数为国王 和每个骑士移动到方格I所 需要的步数。 „ 遍历8x8矩阵中的每一个方 格I，求得国王和每个骑士 到它的最短距离之和。 图论习题课 ACM选讲-最短路径 1）由Floyd算法可以求得国王和每个 骑士到矩阵中的所有方格的最小步 数。 2）Min{ 每个方格i | 国王到i的最小步数 +每个骑士到i的最小步数。 } 图论习题课 ACM选讲-最短路径 „ ACM 1158 „ 题目描述： „ 城市有若干条街道，每个街道的两端有信号 灯，每个信号灯都有两种颜色。当街道两端 的信号灯颜色一致时，道路才通。已知条件 为街道和每个信号灯初始颜色，以及颜色改 变的频率。求给定两端点的最小行车时间？ 图论习题课 ACM选讲-最短路径 „ 题目描述： „ 如图 „ 求1到4的最短行车时间