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