noip模拟试题.doc

A 道路建设(road)TL:1S ML:128MB【Description】A省有N座城市。很久之前，省政府要求每座城市建设一条到其他任意一座城市的道路。也就是说，a市到b市的道路，不是由a市建设的，就是由是b市建设的，每个城市最多建立一条道路。但是由于各种原因，原本的建造N条道路的计划可能并没有被完成。最终只有M条道路被建出。现在kAc已经知道了这M条道路的两端是哪两座城市。他想知道，一共有多少种不同的建造方案，答案对1000000007取模输出。如果你认为不存在合法的方案，输出0。(注：两种方案视为是不同的，当且仅当有至少一条道路是由不同的城市建立的)【Input】第一行两个正整数N, M接下来M行每行两个正整数a, b。表示一条道路的两端是a,b两座城市，保证a不等于b。【Output】一个整数，表示对1000000007取模后的方案数。【Sample Input】5 41 23 24 54 5【Sample Output】6【Hint】6种方案如下2, 3, 4, 52, 3, 5, 41, 3, 4, 51, 3, 5, 41, 2, 4, 51, 2, 5, 4其中第i个数表示第i条道路是由谁建设的对于20%：N, M=20对于另外30%：保证每个连通分量都是一棵树对于另外30%：保证每个连通分量都是一个环对于100%：N, M = 200000B 航班(flight)TL:2S ML:128MB【Description】B国有N座城市，其中1号是这座国家的首都。N座城市之间有M趟双向航班。i号点的转机次数定义为：从1号点到i，最少需要转机几次。如果1根本无法到达i，那么i点的转机次数是无穷大。由于天气原因，有些航班会被取消。一趟航班的取消是可容忍的，仅当这趟航班取消之后，2.N每个点的转机次数不变或者只增加了1。现在kAc想知道，哪些航班的取消是可容忍的？如果这样的航班不存在，输出一行“hehe”(不含引号)【Input】第一行两个正整数N, M接下来M行每行两个正整数a, b。表示当前这趟航班的两端是a,b两座城市，保证a不等于b，且同一对a, b只会出现一次。【Output】若干整数，从小到大排序，表示所有的可容忍取消的航班序号。【Sample Input】5 61 21 31 43 42 53 5【Sample Output】23456【Hint】如果1、2两座城市间的航班被取消，2号城市到首都原本需要0次转机(有直达飞机)，现在需要先到5，再到3，再到1，转机2次。这是不可忍受的。对于40%：N, M=500对于70%：N=500 M = 50000对于100%：N, M=200000保证初始给定图中所有点的转机次数不是无穷大。C 滑雪(ski)TL:3S ML:128MB【Description】C市有一座滑雪场，该滑雪场内一共有N座山。这N座山有各自的高度，第i座山高度用Hi表示。N座山之间已经有M条滑雪道，每条滑雪道都有自己的距离。不过，从一座山只能滑雪到不高于自己的另一座山。换句话说，如果两座山高度不同，滑雪道是单向的；如果两座山的高度相同，那么滑雪道是双向的。kAc站在1号山上。他手里有很多时间剂(可以视作无穷多)。时间剂的用处是回到你曾经所在的一座山。他想知道，在时间剂的帮助下，他最多可以到达多少山。进一步的，在保证到达的山最多的前提下，他最少需要的滑雪距离是多少。(使用时间剂不会增加滑雪距离)【Input】第一行两个正整数N, M接下来N个正整数，表示Hi接下来M行，每行三个正整数，分别表示这条滑雪道的两端以及长度【Output】两个正整数 表示你可以到达的山的数量，以及最少的滑雪距离【Sample Input】3 33 2 11 2 12 3 11 3 10【Sample Output】3 2【Sample Input】3 32 2 11 2 22 1 11 3 10【Sample Output】3 11【Hint】对于样例1：一种可行的方案是：初始在1，先到2，再到3 总距离2对于样例2：一种可行的方案是：初始在1，通过第二条滑雪道到2，用时间剂回到1，再滑雪到3。请注意，当kAc在2的时候，滑雪到1也是可以的，但是这样会导致答案不优。对于30%：N=2000对于100%：N, M=1000000对于每个