findthemostcomfortableroad并查集+贪心-创新互联

并查集 + 贪心

想了很久以变形的dijkstra实现 但发现不行  因为我们贪心的涉及两个数 大值 最小值  不能将两者确定

公司主营业务：成都网站设计、成都网站建设、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。创新互联公司是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联公司推出合浦免费做网站回馈大家。

如果贪心当前的差值最小 显然是欠妥的

并查集 中 的find 是回溯很关键 其实每次merge后 fa数组还没变化的 但要find了才会更新

View Code

find the most comfortable road

Time Limit :1000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) :2   Accepted Submission(s) : 2
Font: Times New Roman| Verdana | Georgia
Font Size: ← →
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

View Code

#include <stdio.h>
#include<stdlib.h>
#include<algorithm>

using std::sort;
const int INF = 0x3f3f3f3f;
int n, m, ans, fa[105];
struct node
{
int a, b, w;
}edge[1005];
void init()
{
for(int i=1; i<=n; i++)
        fa[i]= i;
}
int find(int t)
{
if( fa[t] == t )
return t;
else 
   return fa[t] = find(fa[t]);
}
void merge(int x, int y)
{
int fx = find(x);
int fy = find(y);
if( fx == fy )
return ;
else if( fx < fy )
        fa[fy]= fx;
else
        fa[fx]= fy;
}
int cmp(node a, node b)
{
return a.w <= b.w ;
}
int min(int a, int b)
{return a<=b ?a :b ; }
int main()
{
int i, j, q, src, des;
while(scanf("%d %d", &n, &m)!=EOF)
    {
for(i=1; i<=m; i++)
            scanf("%d %d %d", &edge[i].a, &edge[i].b, &edge[i].w);
        sort( edge+1, edge+1+m, cmp );
        scanf("%d", &q);
while( q-- )
        {
            scanf("%d %d", &src, &des);
            ans= INF;
for(i=1; i<=m; i++)
            {
                init();
for(j=i; j<=m; j++)
                {
                    merge(edge[j].a, edge[j].b);
if(find(src) == find(des))
                    {
                        ans= min(ans, edge[j].w-edge[i].w);
                    }
                }
            }
            printf("%d
", ans==INF?-1:ans);
        }
    }
    
return 0;
}

文章名称：findthemostcomfortableroad并查集+贪心-创新互联
文章路径：https://www.cdcxhl.com/article20/diicco.html

成都网站建设公司_创新互联，为您提供网站排名、网站内链、响应式网站、企业建站、商城网站、动态网站

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联