图论练习题.doc

图论练习题题目名称出门旅行关闭道路重新关闭道路小S的数列游戏提交文件Tour.pas/cpp/cRoad.pas/cpp/cAgain.pas/cpp/cGame.pas/cpp/c输入文件Tour.inRAGame.in输出文件Tour.outRoad.outAgain.outGame.out时间限制1s1s2s1s空间限制128MB128MB128MB128MB考试时间8：0011：00评测时间11：00文件名不区分大小写。评测环境为windows。出门旅行【题目描述】在神奇的oi国度，有n个城市m条双向道路，每条道路连接了两个不同的城市。寒假到了，小S决定出门旅游一趟。因为以往跟团旅游多了，这次小S决定自驾游。对于自驾游，小S最关心的自然是燃油的耗费，为了省钱，小S请你帮他找一条最短的路。【输入格式】第一行两个整数n,m，表示有n个城市和m条双向道路。城市从1.n编号。接下来m行，每行三个正整数a,b,c，表示a和b之间有一条长为c的双向道路。a,b不相同，且c不超过1000注意：两个城市之间可能会有多条双向道路。接下来一行两个整数，s,t，表示小S本次旅行的出发地和目的地。s,t不相同。【输出格式】仅一行一个整数，表示最短的距离。如果不能到达，请输出-1。【样例输入】3 31 2 11 3 32 3 11 3【样例输出】2【样例解释】123即是最优解。【数据范围】对于30%的数据，n=100,m=1000对于100%的数据，n=2000,m=100000关闭道路【题目描述】在神奇的oi国度，有n个城市m条双向道路，每条道路连接了两个不同的城市。由于金融危机，oi国不得不关闭尽量多道路，来减少维护道路的花费。但是为了尽量小地影响到原来的交通，所以要保证，如果在关闭道路前从第i个城市沿着道路走可以到第j个城市，那么关闭道路后依然也可以。求最多能关闭多少道路。【输入格式】第一行两个整数n,m，表示有n个城市和m条双向道路。城市从1.n编号。接下来m行，每行两个不同的1.n的整数，表示这两个城市之间有双向道路相连。注意：两个城市之间可能会有多条双向道路。【输出格式】仅一行，包含一个整数，表示最多能关闭多少条道路。【样例输入】3 31 22 33 2【样例输出】1【样例解释】删去任意一条边均可。【数据范围】对于30%的数据，m=20,n=10对于100%的数据，n=1000,m=100000重新关闭道路【题目描述】在关闭道路后，刚旅游完的小S听说了官方关闭道路的方法，就研究了有没有更优的方案。小S发现，每条道路的维护费用是不同的，在多种关闭最多条道路的方案中，存在着最优的方案，而政府却没有注意到！于是小S将这个发现告诉了你，请你帮他计算下最优的方案可以节省多少维护费用。注意这个最优方案要满足上一题中的条件。【输入格式】第一行两个整数n,m，表示有n个城市和m条双向道路。城市从1.n编号。接下来m行，每行三个正整数a,b,c，表示a和b之间有一条维护费用为c的双向道路。a,b不相同，且c不超过1000注意：两个城市之间可能会有多条双向道路。【输出格式】仅一行一个整数，表示最多节省多少维护费用。【样例输入】3 31 2 12 3 23 2 3【样例输出】3【样例解释】删去第三条边，即可节省3的花费。【数据范围】对于20%的数据，m=20,n=10对于90%的数据，n=1000,m=10000对于100%的数据，n=100000,m=1000000小S的数列游戏【题目描述】小S在解决了关闭道路问题后，受到了政府的嘉奖，很是高兴。回到学校后便和小Z开始玩了数列游戏，小Z写完一个长度为n的数列Z1.n，然后问小S一些问题，问题都是求一段区间内的数字的和。由于小S的计算能力十分强大，所以每次都答对。小Z很不爽，于是只告诉小S一些区间的和。然后再来问小S问题。这下可把小S难倒了，于是小S来求助于你，让你帮他回答问题。【输入格式】第一行两个数n,m，表示数列的长度是n，而现在已知有m个问题的答案。接下来m行，描述了m个问题和答案。每行三个整数a,b,c，表示Za+Za+1+Zb=c。接着是一个整数Q，表示还有Q个问题要回答。接下来Q行，描述了Q个要回答的问题。每行两个整数a,b，表示要求出Za+Za+1+Zb的值。【输出格式】共Q行，每行一个整数，表示对应问题的答案。如果根据已知的m个问题无法得出这个问题的答案，则该行输出“Too Hard”。（不需要