hdu-1875 畅通工程再续---MST

题目链接：

题目大意：

相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！经过考察小组RPRush对百岛湖的情况充分了解后，决定在符合条件的小岛间建上桥，所谓符合条件，就是2个小岛之间的距离不能小于10米，也不能大于1000米。当然，为了节省资金，只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。

解题思路：

和hdu-1863类似，也是MST加连通

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn =  + ;

 const int INF = 1e9 + ;

 double Map[maxn][maxn];

 double lowcost[maxn];

 int mst[maxn];

 int n, m;

 double prim(int u)

 {

     double ans = ;

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

     {

         lowcost[i] = Map[u][i];

         mst[i] = u;

     }

     mst[u] = -;

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

     {

         double minn = INF - ;

         int v = -;

         //寻找lowcost数组里面的未加入mst的最小值

         for(int j = ; j <= n; j++)

         {

             if(mst[j] != - && lowcost[j] < minn)

             {

                 v = j;

                 minn = lowcost[j];

             }

         }

         if(v != -)

         {

             mst[v] = -;

             ans += lowcost[v];

             for(int j = ; j <= n; j++)

             {

                 if(mst[j] != - && lowcost[j] > Map[v][j])

                 {

                     lowcost[j] = Map[v][j];

                     mst[j] = v;

                 }

             }

         }

         else return -1.0;//没有找到，说明不连通

     }

     return ans;

 }

 struct node

 {

     int x, y;

 }a[maxn];

 double dis(node a, node b)

 {

     return sqrt(1.0 * (a.x - b.x) * (a.x - b.x) + 1.0 * (a.y - b.y) * (a.y - b.y));

 }

 int main()

 {

     int T;

     scanf("%d", &T);

     while(T--)

     {

         scanf("%d", &n);

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

             for(int j = ; j <= n; j++)Map[i][j] = INF * 1.0;

         memset(lowcost, , sizeof(lowcost));

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

         {

             scanf("%d%d", &a[i].x, &a[i].y);

         }

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

         {

             for(int j = i + ; j <= n; j++)

             {

                 double d = dis(a[i], a[j]);

                 if(d <  || d > )continue;

                 Map[i][j] = Map[j][i] = d;

             }

         }

         double ans = prim();

         if(ans > )printf("%.1f\n", ans * );

         else printf("oh!\n");

     }

     return ;

 }

巴特西

hdu-1875 畅通工程再续---MST

最新文章

热门文章