《图论进阶几道题.doc》由会员分享，可在线阅读，更多相关《图论进阶几道题.doc（5页珍藏版）》请在金锄头文库上搜索。
1、源文件shu1.pas/exeshu2.pas/exetravel.pas/exeisland.pas/exe输入文件Shu1.inShu2.inTravel.inIsland.in输出文件Shu1.outShu2.outTravel.outIsland.out时限1s1s2s1s空限128M128M128M128M图论进阶几道题（最短路+最小生成树部分）-hjl收集整理1.时间：1s空间：128M 题目描述已知一个无向图，选择n-1条边，使得每两点之间可以互相到达（答案保证有解），求n-1条边的权值和最小是多少？输入格式 第一行两个整数n，m。表示图的的结点数和边数。(n100，m10000
2、)。接下来的m行每行描述了一个边的状况，包含三个整数（U,V,W）,W表示该边的权值且大于等于0.输出格式 一个整数，表示最小值。输入样例3 31 2 12 3 11 3 5输出样例22.时间：1s 空间：128M题目描述：随着ls校园网的壮大，管理员的数目也越来越多，现在你身为管理层的联络员，希望你找到一些通信渠道，使得管理员两两都可以联络（直接或者是间接都可以）。你要尽可能的使费用少才可以。 目前你已经知道，网站通信渠道分为两大类，一类是必选通信渠道，无论价格多少，你都需要把所有的都选择上；还有一类是选择性的通信渠道，你可以从中挑选一些作为最终管理员联络的通信渠道。数据保证给出的通行渠道可
3、以让所有的管理员联通。输入格式 第一行n，m表示一共有n个管理员，有m个通信渠道第二行到m+1行，每行四个非负整数，p,u,v,w 当p=1时，表示这个通信渠道为必选通信渠道；当p=2时，表示这个通信渠道为选择性通信渠道；u,v,w表示本条信息描述的是u，v管理员之间的通信渠道，u可以收到v的信息，v也可以收到u的信息，w表示费用。输出格式最小的通信费用样例输入5 61 1 2 11 2 3 11 3 4 11 4 1 12 2 5 102 2 5 5样例输出9数据范围和注释样例解释：1-2-3-4-1存在四个必选渠道，形成一个环，互相可以到达。需要让所有管理员联通，需要联通2和5号管理员，选
4、择费用为5的渠道，所以总的费用为9注意：U,v之间可能存在多条通信渠道，你的程序应该累加所有u,v之间的必选通行渠道数据范围：对于30%的数据，n=10 m=100对于50%的数据, n=200 m=1000 对于100%的数据，n=2000 m=100003.时间：2s空间：128M题目描述 wxc突发奇想，要去G地，于是他搞来了一张地图，看怎么走才好。地图上有很多城市，G地也是一座城市。每两座城市之间都可能有直达方法，也有可能两座城市之间并不能直接相通，而要通过其他的城市转达。对于两个城市之间的直达方法，需要一定的时间，当然，如果从A城市到B城市的直达方法需要T时间，那么从B城市到A城市的
5、直达方法也是T时间。wxc想要用最短的时间到达G地，但是有个问题，他发现，地图上有些城市对他很有吸引力。所以他要在经过这些城市的基础上时间最短。wxc已经用1、2、3、4、5n标记了他可能经过的城市（1代表出发地，n代表G地），但是眼花缭乱的地图让他感到烦恼。他请你来解决这个问题，告诉他最小需要多少时间到达G地。输入格式输入文件的第一行是三个正整数n和m，t，n表示总共有多少个城市（包括出发地和G地），城市数不会超过200个；m是城市的直达路线数（1=m=20000），t表示一定去的城市数0=t=10（不包括出发地和G地）。接下来一行有t个整数，表示一定要去的城市。接下来m行，每行包含三个正整
6、数，前两个数表示分别代表一个城市，第三个数是这两个城市之间的直达时间。直达时间不会超过1000000。输出格式输出一个数，题目要求的得最短时间。输入样例travel.in5 10 22 31 2 51 3 451 4 611 5 812 3 92 4 912 5 43 4 743 5 424 5 61输出样例travel.out274.问题描述时间：1s空间：128M话说yzy阴差阳错地来到了神秘岛。不久，他们发现，这是一个由n个小岛和一个中心岛组成的群岛，群岛之间有m座桥。令他们感到惊讶的是，这些桥并不是固定不变的，经较长时间的观察，发现它们会随时间作周期性的变化（即桥的两端会不断更换）。
7、yzy很早就留意到远远的那个中心岛了。他们发现岛的上空好像有一个很巨大的东西，但实在太远了，看不清楚。此时他们得意地从身上拿出一个超高倍数望远镜，好像很自豪的样子，因为他们平时专门用来看美女的工具此时终于派得上用场了。“那是一间小屋！架在一棵好大好大的树上！”“yzy！我们也许可以暂时在那安顿，好用来遮风避雨！”于是他们便决定前往中心岛上的那间空中楼阁。yzy的懒惰是出了名的，他们当然希望越早到越好，那么，你能帮帮他们吗？为方便计算，yzy把小岛按1.n编号，0表示中心岛。yzy一开始在编号为1的小岛上。在岛上行走的时间忽略不计，过桥的时间为1个单位。岛上的桥变化的周期为T，在nT+i(n=0
8、,1,2,;i=1,2,T)时刻岛上的桥为第i种状态，一开始的时刻为1。两个小岛间可能有多条桥相连。在任一时刻，yzy可以选择过桥，也可以原地不动。当然，如果无桥可过，yzy只能在原地等待。输入格式输入文件island.in的第一行包括三个整数n（1=n=80），m(1=m=10000)和T(1=T=10)，分别表示小岛的个数，岛上桥的数量和桥改变的周期T。 接下来分别描述第1.T种状态，每种状态有m行，每行有两个整数a, b（0=a,b=n），表示这种状态时小岛a和b有一条桥相连。两状态之间用一空行隔开。输出格式输出文件island.out仅有一个整数，表示yzy最少得花多少时间到达中心岛。如果yzy无法到达中心岛，则输出“Poor yzy!”。输入样例14 5 21 21 31 42 04 01 31 32 34 33 0输出样例12输入样例27 3 21 21 46 02 53 64 7输出样例2Poor yzy!HINT（良心提示大神无视）1,2最小生成树3,4最短路
