HDU 1598 find the most comfortable road(枚舉+最小生成樹)

find the most comfortable road

題目鏈接：Click Here~

題目分析:

要求你找出一條可以從起點到達終點的路。而且這條路滿足最大值與最小值的差盡量的小。一開始的時候我用的是二分+DFS+矩陣存儲。我算了一下時間復雜度為O（1.6*10^6），而且搜索的時候剪枝一下是可以過的。但是提交時TEL，後來我以為是矩陣存儲超時。改用了容器加鏈接表，還是同樣的結果。真郁悶！！！我算過時間復雜度才為O（8*10^5）不知道為什麼過不了！！！被改題卡了一個早上！最後也沒想出來，還是看了別人的解釋。明天就要比賽了，可是前兩天就得了重感冒。有種天要亡我的感覺！看來要帶病上陣了。T_T

算法分析：

可以枚舉每一個可能的起點，因為我們的生成樹是用Kruscal的。所以，算法本身就已經排好序了。我們枚舉每一個可能的起點建起一棵樹，其實也不是一顆完整的樹，因為，一找到起點和終點就可以跳出了。這個要自己好好想想為什麼？其實，這題的本質我個人感覺就是考的一個算法的構造能力。這就要考驗你對算法的理解深度和當時的人品了，哈哈開玩笑。

#include 
#include 
#include 
#include 
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;
}