hdu-1598 find the most comfortable road---kruskal+枚举下界

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1598

题目大意：

XX星有许多城市，城市之间通过一种奇怪的高速公路SARS(Super Air Roam Structure---超级空中漫游结构）进行交流，每条SARS都对行驶在上面的Flycar限制了固定的Speed，同时XX星人对 Flycar的“舒适度”有特殊要求，即乘坐过程中最高速度与最低速度的差越小乘坐越舒服 ,(理解为SARS的限速要求，flycar必须瞬间提速/降速，痛苦呀 ),
但XX星人对时间却没那么多要求。要你找出一条城市间的最舒适的路径。(SARS是双向的）。

解题思路：

对边进行排序，从小到大枚举下界，依次加入每条边，知道恰好目标点连通，那么正好是最大值-最小值。答案取最小值

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn =  + ;

 const int INF = 0x3f3f3f3f;

 struct node

 {

     int u, v, w;

     bool operator <(const node & a)const

     {

         return w < a.w;

     }

 }a[maxn];

 int p[maxn];

 void init()

 {

     for(int i = ; i < maxn; i++)p[i] = i;

 }

 int Find(int x)

 {

     return x == p[x] ? x : p[x] = Find(p[x]);

 }

 void Union(int x, int y)

 {

     p[Find(x)] = Find(y);

 }

 int main()

 {

     int n, m;

     while(cin >> n >> m)

     {

         for(int i = ; i < m; i++)

         {

             cin >> a[i].u >> a[i].v >> a[i].w;

         }

         sort(a, a + m);

         int t, u, v;

         cin >> t;

         while(t--)

         {

             cin >> u >> v;

             int ans = INF;

             for(int start = ; start < m; start++)

             {

                 init();

                 for(int end = start; end < m; end++)

                 {

                     Union(a[end].u, a[end].v);

                     if(Find(u) == Find(v))

                     {

                         ans = min(ans, a[end].w - a[start].w);

                     }

                 }

             }

             if(ans < INF)cout<<ans<<endl;

             else cout<<"-1"<<endl;

         }

     }

     return ;

 }

巴特西

hdu-1598 find the most comfortable road---kruskal+枚举下界

最新文章

热门文章