首页 > 代码库 > hdoj 1598 find the most comfortable road 【并查集】+【暴力枚举】

hdoj 1598 find the most comfortable road 【并查集】+【暴力枚举】

2024-08-01 19:38:08   211人阅读

find the most comfortable road

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4022    Accepted Submission(s): 1732



Problem Description
XX星有许多城市，城市之间通过一种奇怪的高速公路SARS(Super Air Roam Structure---超级空中漫游结构）进行交流，每条SARS都对行驶在上面的Flycar限制了固定的Speed，同时XX星人对 Flycar的“舒适度”有特殊要求，即乘坐过程中最高速度与最低速度的差越小乘坐越舒服 ,(理解为SARS的限速要求，flycar必须瞬间提速/降速，痛苦呀 ),
但XX星人对时间却没那么多要求。要你找出一条城市间的最舒适的路径。(SARS是双向的）。
 


Input
输入包括多个测试实例，每个实例包括：
第一行有2个正整数n (1<n<=200)和m (m<=1000),表示有N个城市和M条SARS。
接下来的行是三个正整数StartCity,EndCity,speed,表示从表面上看StartCity到EndCity,限速为speedSARS。speed<=1000000
然后是一个正整数Q（Q<11),表示寻路的个数。
接下来Q行每行有2个正整数Start,End, 表示寻路的起终点。
 


Output
每个寻路要求打印一行，仅输出一个非负整数表示最佳路线的舒适度最高速与最低速的差。如果起点和终点不能到达，那么输出-1。
 


Sample Input
4 41 2 22 3 41 4 13 4 221 31 2
 


Sample Output
10


分析：先按照速度从小到大排序，然后从当前i开始到n建立并查集，直到初始和目的形成连接，然后与ans比较

代码：

[cpp] view plaincopy在CODE上查看代码片派生到我的代码片
    1. /*hdoj 1598*/   
    2. #include <stdio.h>  
    3. #include <string.h>  
    4. #include <algorithm>  
    5. #define M 1005  
    6. #define INF 0x3f3f3f3f  
    7. using namespace std;  
    8.   
    9. struct node{  
    10.     int from, to, sp;  
    11. }s[M];  
    12. int fat[M], n, m;  
    13.   
    14. int f(int x){  
    15.     if(fat[x] != x) fat[x] = f(fat[x]);  
    16.     return fat[x];  
    17. }  
    18.   
    19. int cmp(node a, node b){  
    20.     return a.sp<b.sp;      
    21. }  
    22.   
    23. int main(){  
    24.     int i, a, b, c, j, q;  
    25.     while(scanf("%d%d", &n, &m) == 2){  
    26.         for(i = 0; i < m; i ++)  
    27.             scanf("%d%d%d", &s[i].from, &s[i].to, &s[i].sp);  
    28.         sort(s, s+m, cmp);  
    29.           
    30.         scanf("%d", &q);  
    31.         while(q --){  
    32.             int ans = INF;  
    33.             scanf("%d%d", &a, &b);  
    34.             for(i = 0; i < m; i ++){  
    35.                 for(j = 1; j <= n; j ++) fat[j] = j;  
    36.                 for(j = i; j < m; j ++){  
    37.                     int x = f(s[j].from);  
    38.                     int y = f(s[j].to);  
    39.                     if(x!=y) fat[x] = y;  
    40.                     if(f(a) == f(b)){  
    41.                         ans = min(ans, s[j].sp-s[i].sp); break;  
    42.                     }  
    43.                 }  
    44.             }  
    45.             if(ans == INF) printf("-1\n");  
    46.             else printf("%d\n", ans);  
    47.         }  
    48.     }  
    49.     return 0;  
    50. } 

hdoj 1598 find the most comfortable road 【并查集】+【暴力枚举】


联系
我们