河海大学ACM专题第六周-最短路题解

编程与算法

本周题目主要是联系最短路径的几个算法。主要是floyd,dijkstra和Bellman-Ford,最后一题也可以用spfa.

这些算法会重新利用其他文章去解释。

简单说一下这些算法的用法。

floyd是用来计算图中任意一点到其他点的最短路径。写起来也比较简单，时间复杂度为O(n^3).

dijkstra是计算单源最短路径的算法，也就是相当于固定了起点。所以时间复杂度降为O(n^2).

以上两个算法面临权值为负时便无法正常的运行下去，所以为了处理出现负环等情况。使用下面的算法。
Bellman-Ford简单暴力的处理相关问题，没有做任何优化。写起来很简单，用起来也不错。时间复杂度大概为O(ne).
spfa一般是在上面的基础上加上了队列，有的好像加的是优先队列。反正就是效率大大提高就对了。时间复杂度为O(ek).据说k很小。其实我并不知道有多小。

下面来解释一下题目。

problem A poj1125

本题是标准的弗洛伊德。题意是，在一个有向图中，找出从一个点发送消息到其他所有点耗时最小的点和时间。

输入样例第一个n表示图中点的个数。
然后下面有n行数，第i行第一个数m表示：第i个点的出度为m。然后m后面有m对数，每对数有两个值(x,v)，表示i -> x的耗时为v。

输入完成后就可以建立一个有向图。然后对这个图使用Floyd,就可以得到每个点到其他点的最短路径。

然后使用双重循环去找到耗时最小的点和时间即可。

核心就是一个Floyd：

1
2
3
4
5
6
7
8
const int N = 105;
int dis[N][N];
void floyd(int n){
	for(int t=1; t<=n; t++)  
		for(int i=1; i<=n; i++)  
			for(int j=1; j<=n; j++)  
				dis[i][j]=min(dis[i][j],dis[i][t]+dis[t][j]);  
}

problem B poj3615

本题同样是floyd，不过需改修改松弛方程。

dis[i][j]=min(dis[i][j],max(dis[i][t],dis[t][j]));

大概题意如下：

给你n个站，有m条边，每条边有一个耗费值。
问你如果A站到B站可通，选一条路，求路径上的相邻两站的耗费值的最大值，让这个值最小，输出。
否则输出-1.

其实也就是先用floyd预处理，然后直接去查询。一般遇到多组查询都可以考虑先预处理然后离线查询。

problem C poj1847

该题就变成了单源的最短路径了，所以可以使用dijkstra去求解。

首先解释一下题意。就是火车从一点开到另外一点。在中途会经过火车站，每个站点有多个出口，
其中有一个默认的方向，如果走默认方向则不需要消耗，如果走其他方向便需要进行一次切换。
问最少切换几次可以到达终点。到不了输出-1.

这道题可以进行一些理解，就是，默认方向权值为0，而其他方向权值为1.构造一个有向图。

输入n a b,n表示车站数，a表示出发站点，b表示终点。
下面有n行，每行第一个数为m,后面紧跟m个数，其中第一个是默认方向，其他为需要切换的方向。

根据输入建立了有向图。然后对图使用dijkstra，最后得到最短路径。

代码也不难，注意初始化就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const int N = 105;
const int INF = 0x1f1f1f1f;

int map[N][N];
int dis[N];
bool visit[N];

void dijkstra(int st,int n){
	memset(dis,INF,sizeof(dis));
	memset(visit,0,sizeof(visit));
	for(int i=1;i<=n;i++){
		dis[i] = map[st][i];
	}
	dis[st] = 0;
	visit[st] = 1;
	int minx = INF;
	int index = st;
	for(int i=1;i<=n;i++){
		minx = INF;
		for(int j=1;j<=n;j++){
			if(!visit[j] && dis[j] < minx){
				minx = dis[j];
				index = j;
			}
		}
		if(minx == INF)
			break;
		visit[index] = 1;
		for(int j=1;j<=n;j++){
			if(dis[j] > map[index][j] + minx){
				dis[j] = map[index][j] + minx;
			}
		}
	}
}

##　problem D poj1502
这道题也是一个普通的dijkstra,具体题意同problem A,只不过变成单源的了。但是因为数据并不强所以用floyd同样可以过。

输入的不是常规输入，而是直接按照邻接三角矩阵给出(x表示正无穷)。例如：

1
2
3
4
5
0   50 30 100 10
50  0  5  20  x
30  5  0  50  x
100 20 50 0   10
10  x  x  10  0

输入中把0忽略。

还有就是在杭电平台是可以使用atoi()函数的，所以不要定义和他名字相同的函数，否则会RE。

problem E poj1860

本题就是会出现负环(正环)的题目，好像用dijkstra加上优化也可以过，不过更通用的还是用Bellman-Ford或spfa。

本体大意为：有n种货币(点)和2*m个货币兑换点(边)，边(a -> b)的权值为(V-Cab) × Rab.我们需要找到是否存在一种兑换使我们的本金不断增加。

其实就是找到一个不断增加的回路，也就是说找到权值最大路径。如果经过n-1次循环后，仍然满足松弛条件，则该图存在负环(正环)。也就是满足我们需要的条件，输出YES.

大概就是这个样子的。具体算法详见其他文章。