算法竞赛入门经典 图论部分题解

/ 0评 / 0

UVa 10801 电梯换乘

题意:

有5个以内电梯,分别可以到达不同的楼层,且速度不同,同一层次如果有两部电梯,就可以换乘,从一部电梯到任意一部电梯都花60s。求0层到某层花费的时间。

解法:

开始我想到的是把每一层不同的电梯看成一个点,但是建图会非常麻烦。看见网上题解用邻接矩阵,代码很简洁。
把每一层视为一个点,邻接矩阵储存每一个点i到另一个点j的最短距离,这个最短距离是未换乘的最短距离。任意i,j都是用了同一部电梯,但同一行或同一列不一定是同一部电梯。d[]刚好等价于G[0][],接下来就是dijkstra算法,如:G0存在,说明0到i的最短距离就是G0,此时再更新所有邻接点,如果0,j无边,或者换乘后距离小于未换乘的最短距离,那就更新。
原代码在邻接点加了判断vis[y]是为了电梯可以一直向上走。

UVa 1664 Conquer a New Region

题意:

n个城镇,有n-1条路,c(i,j)表示两个城镇之间的交通容量,一条路径的容量的最大值是这条路径所有路的最小值,找出一个中心点,使得它到其他n-1个城镇的容量最大。

解法:

最小生成树的定义是边权总和最小的的生成树。这里并不是求边权总和最大的生成树,而是路径上权最小值,利用Kruskal算法,按照它排序做生成树。怎么求路径最小值?边从大到小排序,如果第一个是(u, v, c),显然u到v的最小权值和v到u的都是等于c,对于新加入的边呢?新加入的(u, v1, c1),和u,v属于同一个连通分量,那么c1肯定是u到v1和v到v1的最小权值,因为是从大到小排序。本来想的是计算每一个点的到其他点的权值和,然后排序找最大的,在每个连通分量添加新点时,更新他们的权值和,结果TLE。
看了网上类似贪心的做法,因为不需要求出具体哪个点作为中心,所以在每次添加新点时,比较两个点(孤立点或者连通分量代表元)谁作为中心时会更大,把并查集的代表元改为中心点。
其依据是:每加入一个点,由于排序,它的权值必然小于等于连通分量内所有边的权值,所以当新点作为中心点时,连通分量的每个点都必须加上新点带来的权值。

UVA 1279 Asteroid Rangers

题意:

n个点在三维空间,每个点会匀速移动,在xyz方向上有恒定速度,相同时间每个点都移动到不同坐标,图有唯一的最小生成树,且最小生成树在10^-6s内不会改变,求最小生成树的个数。

解法:

p1(x1 + dx1 t, y1 + dy1t, z1 + dz1 * t)
p2(x2 + dx2 t, y2 + dy2t, z2 + dz2 * t)
IMG_20180114_194304.jpg

UVa Live 6039 Let’s Go Green

题意:

有n个城市,城市与城市构成树形结构(每个城市之间只有唯一一条路)简单起见,自行车不会走同样的路两次(一个城市路过一次),给出每条路上自行车经过的次数,求自行车最少能有多少。

解法1:

先求所有边的权的和sum,sum肯定是大于等于总单车数的,一辆车可以增加很多边权。把输入的单向边变为双向的,这样来遍历每一个点,这里把边权定义为经过边的单车数,让点权值等于经过该点的单车数,发现:点权和 = 边权和 + 最少单车数(难不成这是图论的某个定理?),点权的计算:如果有一条边的权比其余边权的和还要大,即maxm > esum - maxm,那么让这条边的单车往其他边走,点权(经过该点的单车)最少是maxm;如果没有出现这种情况,只能让边上的自行车的一半,经过该点然后去抵消另一半边,偶数自行车一半到另一半,奇数有一个在该点经过就不走了,剩下的一半去抵消另一半,对于整形除法都是(esum + 1) / 2。

发表评论

电子邮件地址不会被公开。 必填项已用*标注