2015福州夏令营7.16图论测试复件problems

1、7.16 练习赛by lwher共 3 道题目，时间 3 小时题目名必经道路修建虫洞源文件输入文件输出文件时间限制内存限制测试点测试点分值bjzl.cpp/c/pasdvalue.cpp/c/pasholes.cpp/c/pasbjzl.indvalue.inholes.inbjzl.outdvalue.outholes.out1000MS1000MS1000MS256MB256MB256MB102010105101. 必经(bjzl.*)【题目描述】农场里，有好多好多的奶牛，但是由于农夫喂养得太好了，奶牛们越来越懒了，导致农夫不得不采取些措施：要求它们每天早上晨跑，从A 农场跑到 B 农场。

2、从 A 农场到 B 农场中有 n2 个路口，分别标上号，A 农场为 1 号，B 农场为 n 号，路口分别为 2.n1 号，从 A农场到 B 农场有很多条路径可以到达，而农夫发现有的路口是必须经过的，即每条路径都经过的路口，农夫要把它们下来，这样农夫就可以先到那个路口，观察奶牛们有没有偷懒，而你的任务就是找出所有必经路口。【输入文件】第一行两个数 n，m。接下来 m 行，每行两个数 u 和 v，表示路口 u 和 v 之间有路径直达。(道路是双向的)输入数据保证必经路口一定存在，并且每个路口都和A，B 农场直接或间接连通。【输出文件】第一行一个数 m，表示必经路口数目。接下来 m 行，按从小到大的

3、顺序依次输出每个必经路口的。（不包括起点，终点）【样例输入】61223456243556【样例输出】225【样例说明】如果不经过结点 2，不能到达终点 6。 如果不经过结点 5，也不能到达终点 6。【数据范围】对于 30%的数据，n 100，m 1000。 对于 100%的数据，n 2000，m 8000。2、道路修建(dvalue.*)【题目描述】D 省后，所有城市之间的道路都损坏了，城市之间的道路需要重修一遍。很多城市之间的地基都被破坏导致不能修公路了，现在给定了一些城市对，在这些城市对之间可以修公路，并且都有相应的价格。而且因为施工队伍有限，所以要求用尽量少的道路将所有的城市起来，这样施

4、工量可以尽量少，道路可视为无向边，且数据保证至少有一种连通的方案。不过，还有一个要求，即在满足上述条件的情况下，选择案，使得该方案中最贵道路的价格和最便宜道路的价格的差值尽量小，即使这样的方案回事总价格很多也没有关系。请安排一种合理的方案，满足以上要求。【输入文件】第一行两个数 n，m，表示城市的个数以及可以修的公路数；第二行开始 m 行，每行三个数a,b,c，表示 a,b 之间可以修一条价值 c 的无向道路。【输出文件】一个数表示该最优方案中最大边减去最小边的值，要求尽量的小。【样例输入】51102938412223345345455691677948336538749366501422【样

5、例输出】1686【样例说明】选第 4,5,6,9 条边即可。【数据范围】对于 30%的数据，n m 20。对于 100%的数据，n m 5000,0 c 50000。3、虫洞(holes.*)【题目描述】N 个虫洞，M 条单向跃迁路径。从一个虫洞沿跃迁路径到另一个虫洞需要消耗一定量的和 1时间。虫洞有白洞和黑洞之分。设一条跃迁路径两端的虫洞质量差为 delta。从白洞跃迁到黑洞，消耗的话，取为 0。从黑洞跃迁到白洞，消耗的值减少 delta，若该条路径消耗的值变为负数的值增加 delta。3.路径两端均为黑洞或白洞，消耗的值不变化。作为压轴题，自然不会是如此简单的最短路问题，所以每过 1白洞变

6、为黑洞。在飞行过程中，可以选择在一个虫洞停留 1 个时间黑洞变为白洞，时间，如果当前为白洞，则不消耗，否则消耗 si的。现在请你求出从虫洞 1 到 N 最少的消耗，保证一定存在 1 到 N 的路线。【输入格式】第 1 行：2 个正整数 N,M第 2 行：N 个整数，第 i 个为 0 表示虫洞 i 开始时为白洞，1 表示黑洞。第 3 行：N 个整数，第 i 个数表示虫洞i 的质量 wi。第 4 行：N 个整数，第 i 个数表示在虫洞 i 停留消耗的si。第5.M+4 行：每行 3 个整数，u,v,k，表示在没有影响的情况下，从虫洞 u 到虫洞 v 需要消耗k。【输出格式】一个整数，表示最少的消耗。【样例输入】4 51 0 1 010 10 100 1