并查集 + 貪心

想了很久以變形的dijkstra實現(xiàn) 但發(fā)現(xiàn)不行  因為我們貪心的涉及兩個數(shù) 大值 最小值  不能將兩者確定

公司主營業(yè)務(wù)：成都網(wǎng)站設(shè)計、成都網(wǎng)站建設(shè)、移動網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。創(chuàng)新互聯(lián)公司是一支青春激揚、勤奮敬業(yè)、活力青春激揚、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團(tuán)隊有機會用頭腦與智慧不斷的給客戶帶來驚喜。創(chuàng)新互聯(lián)公司推出合浦免費做網(wǎng)站回饋大家。

如果貪心當(dāng)前的差值最小 顯然是欠妥的

并查集 中 的find 是回溯很關(guān)鍵 其實每次merge后 fa數(shù)組還沒變化的 但要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---超級空中漫游結(jié)構(gòu)）進(jìn)行交流，每條SARS都對行駛在上面的Flycar限制了固定的Speed，同時XX星人對 Flycar的“舒適度”有特殊要求，即乘坐過程中高速度與最低速度的差越小乘坐越舒服 ,(理解為SARS的限速要求，flycar必須瞬間提速/降速，痛苦呀 ),
但XX星人對時間卻沒那么多要求。要你找出一條城市間的最舒適的路徑。(SARS是雙向的）。
Input
輸入包括多個測試實例，每個實例包括：
第一行有2個正整數(shù)n (1<n<=200)和m (m<=1000),表示有N個城市和M條SARS。
接下來的行是三個正整數(shù)StartCity,EndCity,speed,表示從表面上看StartCity到EndCity,限速為speedSARS。speed<=1000000
然后是一個正整數(shù)Q（Q<11),表示尋路的個數(shù)。
接下來Q行每行有2個正整數(shù)Start,End, 表示尋路的起終點。
Output
每個尋路要求打印一行，僅輸出一個非負(fù)整數(shù)表示最佳路線的舒適度高速與最低速的差。如果起點和終點不能到達(dá)，那么輸出-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并查集+貪心-創(chuàng)新互聯(lián)
文章路徑：http://chinadenli.net/article20/diicco.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站排名、網(wǎng)站內(nèi)鏈、響應(yīng)式網(wǎng)站、企業(yè)建站、商城網(wǎng)站、動態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)