随笔-65  评论-6  文章-0  trackbacks-0
 1 /*
 2 Author:    Leo.W
 3 Descriptipn:  城市间的道路通行,寻找从A城到B城,其间经过的路线最高速与最低速极差最小的路线,并输出这个最小值。 
 4 How to Do:    并查集(最小生成树的Kruskal算法)+ 贪心;
 5               先将道路权值自小到大排序,再依次枚举权值下限,每次枚举一个下限时,初始化一次,然后Kruskal算法
 6               直到A、B两点被连通,记录这一路的极值。接着循环枚举下一个下限,即比前一个下限大一点的权值。直到
 7               所有权值被枚举完,此时极值中的最小值就得到了。
 8   */
 9 #include <cstdio>
10 #include <iostream>
11 #include <algorithm>
12 #include <string.h> 
13 using namespace std;
14 #define INF 0x7fffffff
15 #define MAXD 205
16 #define MAXN 1005
17 struct line{
18     int bg;
19     int ed;
20     int val;
21 }road[MAXN];
22 int par[MAXD],rank[MAXD];
23 int n,m;
24 
25 int cmp(line a,line b){
26     return a.val<b.val;
27 }
28 int findSet(int x){
29     if(x!=par[x])
30         par[x]=findSet(par[x]);
31     return par[x];
32 }
33 bool Union(int x,int y){
34     x=findSet(x);
35     y=findSet(y);
36     if(x==y)    return false;
37     if(rank[x]>rank[y])
38         par[y]=x;
39     else{
40         if(rank[x]==rank[y])
41             rank[y]++;
42         par[x]=y;
43     }
44     return true;
45 }
46 inline void makeSet(int n){
47     int i;
48     for(i=1;i<=n;i++)//从1到n
49         par[i]=i,rank[i]=0;
50 }
51 int main(){
52     //freopen("in.txt","r",stdin);
53     while (scanf("%d%d",&n,&m)!=EOF){
54         int i,j;
55         for(i=0;i<m;i++)
56             scanf("%d%d%d",&road[i].bg,&road[i].ed,&road[i].val);
57         sort(road,road+m,cmp);//权值自小到大排序
58         int cases;    
59         scanf("%d",&cases);
60         while (cases--){
61             int st,en,Min=INF;
62             scanf("%d%d",&st,&en);
63             for(i=0;i<m;i++){
64                 makeSet(n);
65                 for(j=i;j<m;j++){
66                     if(Union(road[j].bg,road[j].ed))
67                         if(findSet(st)==findSet(en)){
68                             if(Min>road[j].val-road[i].val)
69                                 Min=road[j].val-road[i].val;
70                             break;
71                         }
72                 }
73             }
74             if(Min!=INF)
75                 printf("%d\n",Min);
76             else
77                 printf("-1\n");
78         }
79     }
80     return 0;
81 }
82 
posted on 2012-03-16 12:26 Leo.W 阅读(346) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理