最近做了两道floyd变种的题目,又加深了对floyd原理的理解.
第1题: bupt 1460 游览路线
http://acm.cs.bupt.cn/onlinejudge/showproblem.php?problem_id=1460大意是给定一个无向图,找出一个环,使得环的长度最短,并且这个环上至少有3个顶点.
一种O(mn^2)的做法是枚举每条边<u,v>,用dijkstra求由原图删去这条边后的新图中u,v间最短路径dist[u,v],该环长度即为map[u,v]+dist[u,v].输出环长度值最小的那个.
仔细分析知道,这题实际上是要求每对点u,v间不包含边<u,v>的最短路径.想到floyd正是计算所有点对最短路径的.但是这里不能包含边<u,v>的条件就是变化所在.
floyd的原理是依次往"中间点集"中加入点k,再更新任意点对dist[i,j].
此题中,如果直接枚举map[i,k]+map[k,j]+floyd[i,j](floyd[i,j]为使用经典算法得到的两点间最短路),有可能出现一个点经过两次的情况.比如由边集{(1,2),(1,3),(1,4)}构成的图,依题意是无解,但是用错误的枚举方法却有解.原因是没有排除(1->2),(2->1->3),(3->1)的情况.此时可以看出,以点k为原点枚举i,j时的floyd[i,j]应该是保证不经过k的,也就是枚举操作应该在往"中间点集"中加入k之前!
这样可以得出算法的大致轮廓:在加入点k前更新dist[i,j]
但是问题是,此时的中间点只有1..k-1,那后面的点k+1..n会不会漏处理呢?
本质上,这题求的是环的长度,而不是路径长度.因此,假如存在一个更短的环,它路径上有k之后的点p1,p2,...,pm,设其中最后处理的那个点是pl.那么这个环一定会在向中间点集中加入pl的那次循环里枚举到.
因此不存在漏解问题.
代码如下:
1 #include <iostream>
2 using namespace std;
3 int N,M,ans;
4 //w是原图矩阵,d是floyd最短路矩阵
5 int w[110][110],d[110][110];
6 int main(){
7 int i,j,k,a,b,c;
8 while(scanf("%d%d",&N,&M)!=EOF){
9 for(i=1;i<=N;i++)
10 for(j=1;j<=N;j++)
11 w[i][j]=d[i][j]=0;
12 for(i=1;i<=M;i++){
13 scanf("%d%d%d",&a,&b,&c);
14 if(!w[a][b]||c<w[a][b]){
15 w[a][b]=w[b][a]=c;
16 d[a][b]=d[b][a]=c;
17 }
18 }
19 ans=0x7fffffff;
20 for(k=1;k<=N;k++){
21 //先枚举map[i,k]+map[k,j]+floyd[i,j]
22 for(i=1;i<k;i++)
23 for(j=i+1;j<k;j++)
24 if(w[i][k]&&w[k][j]&&d[i][j])
25 ans=min(ans,d[i][j]+w[i][k]+w[k][j]);
26 //再向中间点集中加入k并更新floyd矩阵
27 for(i=1;i<=N;i++){
28 if(!d[i][k])continue;
29 for(j=1;j<=N;j++){
30 if(!d[k][j]||i==j)continue;
31 if(!d[i][j]||d[i][j]>d[i][k]+d[k][j])
32 d[i][j]=d[i][k]+d[k][j];
33 }
34 }
35 }
36 if(ans<0x7fffffff)
37 printf("%d\n",ans);
38 else
39 puts("No solution.");
40 }
41 return 0;
42 }
posted on 2009-03-31 14:20
wolf5x 阅读(146)
评论(0) 编辑 收藏 引用 所属分类:
acm_icpc 、
algorithm