程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 1598

hdu 1598

編輯:C++入門知識


可以用並查集,也可以用二分+單元最短距離做。思路都差不多。都是枚舉上下界。先將速度排序。然後枚舉上界,添加其他節點。如果能使a->b聯通,那麼當前這個舒適值就是上界-新添加的這個節點(使a-b聯通的)。
然後求一個最小值就行了。

下面是AC代碼:
[cpp] 
#include<cstdio> 
#include<algorithm> 
using namespace std; 
const int maxn = 210; 
struct node{ 
    int s,e; 
    int speed; 
}road[1010]; 
int fa[maxn]; 
bool cmp(const node a,const node b){ 
     return a.speed>b.speed; 

void init(){ 
    for(int i=1;i<=210;i++) fa[i]=i; 

int find(int x){ 
    if(fa[x]!=x) 
        return find(fa[x]); 
    return fa[x]; 

int main(){ 
    int n,m,Q,a,b; 
    while(scanf("%d%d",&n,&m)!=EOF){ 
        for(int i=0;i<m;i++){ 
           scanf("%d%d%d",&road[i].s,&road[i].e,&road[i].speed); 
        } 
        sort(road,road+m,cmp); 
        scanf("%d",&Q); 
        while(Q--){ 
            int min_val = 0x7fffffff,t_val; 
            scanf("%d%d",&a,&b); 
            for(int i=0;i<m-1;i++){ 
                init();  t_val=0x7fffffff; 
                int s=road[i].s,       e=road[i].e; 
                int fs=find(s);   int fe=find(e); 
                if(fs!=fe){ 
                   fa[fs]=fe; 
                } 
                if(find(a)==find(b)){ 
                    min_val=0; 
                        break; 
                } 
                for(int j=i+1;j<m;j++){ 
                    s=road[j].s;   e=road[j].e; 
                    fs=find(s);   fe=find(e); 
                    if(fs!=fe){ 
                       fa[fs]=fe; 
                    } 
                    if(find(a)==find(b)){ 
                        t_val=road[i].speed-road[j].speed; 
                        break; 
                    } 
                } 
                if(min_val>t_val){ 
                   min_val=t_val; 
                } 
            }   www.2cto.com
 
         if(min_val==0x7fffffff) min_val=-1; 
             printf("%d\n",min_val); 
        } 
    } 
    return 0; 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved