《【调研研究分析报告】1508 Intervals解题报告》由会员分享，可在线阅读，更多相关《【调研研究分析报告】1508 Intervals解题报告（11页珍藏版）》请在金锄头文库上搜索。
1、1508Intervals 差分约束系统 题目描述 给定n个整数闭区间 ai bi 和n个整数c1 cn 编程实现 以标准输入方式读入闭区间的个数 每个区间的端点和整数c1 cn 求一个元素个数最少的整数集合Z 满足 Z ai bi ci 即Z里边的数中范围在闭区间 ai bi 的个数不小于ci个 i 1 2 n 以标准输出方式输出答案 输入 输出描述 输入描述 输入文件的第一行为一个整数n 1 n 50000 表示区间的个数 接下来n行描述了区间 第i 1行包含了3个整数ai bi ci 用空格隔开 0 ai bi 50000 1 ci bi ai 1 输入一直到文件尾 输出描述 每个cas
2、e 输出一个整数 为元素个数最少的Z的元素个数 Z 整数集合Z满足 Z里边的数中范围在闭区间 ai bi 的个数不小于ci个 i 1 2 n 样例输入 输出 样例输入 5 有5个区间373 第1个区间为 37 要求 Z 37 38103 第2个区间为 810 要求 Z 810 368113110111 样例输出 6 差分约束系统求解 构造图求解最短路径case分析1 样例输入 5373810368113110111样例输出 6 数学模型为 设S i 是Z中小于等于i的元素个数 即S i s s Z s ci 转换成S ai 1 S bi 0 即S i 1 M中的M 转换成S0 S11 M 即要
3、求源点S11到S0的最短路径长度 长度为 M 假设最终求得的各顶点到源点S11的最短路径长度保存在数组a 中 那么 M a 0 a 11 即M a 11 a 0 即为所求 与ZOJ2770直接根据约束条件构造网络图求解最短路径的方法不同的是 由于第2 3个约束条件中的不等式有2 mx mn 1 个 再加上约束条件1 构造的边数最多可达3 50000条 所以将所有的约束条件转换成图中的边 不是个好方法 更好的方法是 1 先仅仅用约束条件1构造网络图 各顶点到源点的最短距离初始为0 这是因为Si Smx 0 所以源点到各顶点的最短距离肯定是小于0的 注意本题中源点是S mx 2 即刻用Bellma
4、n Ford算法求各顶点到源点的最短路径 注意Bellman Ford算法的思想 在每次循环是再加上约束条件2和3的判断 求解思路 continue 1 约束条件2的判断 S i S i 1 1等效于S i S mx S i 1 S mx 1假设a i 为源点mx到顶点Si的最短路径 那么S i S mx 就是a i S i 1 S mx 1就是a i 1 1 即如果顶点Si到源点的最短路径长度大于Si 1到源点的最短路径长度加1 则修改a i 为a i 1 1 2 约束条件3的判断 S i 1 S i 等效于S i 1 S mx S i S mx S i S mx 就是a i S i 1 S
5、 mx 就是a i 1 即如果顶点Si 1到源点的最短路径长度大于Si到源点的最短路径 则修改a i 1 为a i 相关变量值区间个数 n 5mx 11mn 1mn 1 0 边的数组edge 各顶点到源点11的最短路径长度数组a 初始 条件2判断 将a i 修改为a i 1 1 条件3判断 将a i 1 修改为a i 条件2判断 条件3判断 Bellman循环 每条边都判断一下 是否会修改最短路径长度 Bellman循环 特别注意 对任意的Si 有 Si S11 0 即从各顶点Si到源点S11的最短路径长度初始为0 case分析2 另外Bellman Ford算法并非一定要循环n 1次或n 2
6、次 n为顶点个数 详见课件中关于Bellman Ford算法的改进 代码 include include defineinf99999 defineEMAX50002structEdge intu v w 边 起点 终点 权值 edge EMAX intn 区间的个数inta EMAX 求得的从源点到各顶点的最短路径intmn 所有区间左端点的最小值intmx 所有区间右端点的最大值voidinit inti for i 0 i EMAX i a i 0 将源点到各顶点的最短路径长度初始为0mx 1 mn inf boolbellman ford inti t f 1 标志变量 为提前结束Bellman Ford算法的标志变量 只要某次循环过程中 没能改变源点到各顶点的最短距离 则可以提前结束while f f 0 Bellman Ford算法本身的循环 考虑每条边是否能改变源点到各顶点的最短距离for i 0 it a edge i v t f 1 根据约束条件s i t a i t f 1 根据约束条件s i 1 mn i t a i if a i 1 t a i 1 t f 1 returntrue intmain while scanf d
