hdu 1598

可以用並查集，也可以用二分+單元最短距離做。思路都差不多。都是枚舉上下界。先將速度排序。然後枚舉上界，添加其他節點。如果能使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; 
}