find the most comfortable road
题目链接：Click Here~
题目分析:
要求你找出一条可以从起点到达终点的路。而且这条路满足最大值与最小值的差尽量的小。一开始的时候我用的是二分+DFS+矩阵存储。我算了一下时间复杂度为O（1.6*10^6），而且搜索的时候剪枝一下是可以过的。但是提交时TEL，后来我以为是矩阵存储超时。改用了容器加链接表，还是同样的结果。真郁闷！！！我算过时间复杂度才为O（8*10^5）不知道为什么过不了！！！被改题卡了一个早上！最后也没想出来，还是看了别人的解释。明天就要比赛了，可是前两天就得了重感冒。有种天要亡我的感觉！看来要带病上阵了。T_T
算法分析：
可以枚举每一个可能的起点，因为我们的生成树是用Kruscal的。所以，算法本身就已经排好序了。我们枚举每一个可能的起点建起一棵树，其实也不是一颗完整的树，因为，一找到起点和终点就可以跳出了。这个要自己好好想想为什么？其实，这题的本质我个人感觉就是考的一个算法的构造能力。这就要考验你对算法的理解深度和当时的人品了，哈哈开玩笑。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 200+5;
const int INF = 1e7;
struct Node{
int from,to,dist;
bool operator<(const Node& a)const{
return dist < a.dist;
}
}edges[maxn*maxn];
int n,m,f[maxn],rank[maxn];
void Init()
{
for(int i = 0;i <= n;++i) f[i] = i;
}
int Find(int x)
{
if(x==f[x])
return f[x];
return f[x] = Find(f[x]);
}
void Union(int u,int v)
{
int a = Find(u),b = Find(v);
if(a != b)
f[a] = b;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i = 0;i < m;++i)
scanf("%d%d%d",&edges[i].from,&edges[i].to,&edges[i].dist);
sort(edges,edges+m);
int q;
scanf("%d",&q);
while(q--){
int u,v,ans = INF;
scanf("%d%d",&u,&v);
for(int i = 0;i < m;++i){
Init();
for(int j = i;j < m;++j){
Union(edges[j].from,edges[j].to);
if(Find(u)==Find(v)){
ans = min(ans,edges[j].dist-edges[i].dist);
break;
}
}
}
if(ans == INF)
puts("-1");
else
printf("%d\n",ans);
}
}
return 0;
}
HDU 1598 find the most comfortable road(枚举+最小生成树),布布扣,bubuko.com
HDU 1598 find the most comfortable road(枚举+最小生成树)
原文：http://blog.csdn.net/zhongshijunacm/article/details/21740489