UVA 10462 Is There A Second Way Left? (次小生成树+kruskal)

题目大意：

　　Nasa应邻居们的要求，决定用一个网络把大家链接在一起。给出v个点，e条可行路线，每条路线分别是x连接到y需要花费w。

　　1：如果不存在最小生成树，输出“No way”.

　　2：如果不存在次小生成树，输出“No second way”.

　　3：如果两者都存在，输出次小生成树的长度.

解题思路：

　　次小生成数+kruskal模板

 #include <cmath>

 #include <queue>

 #include <string>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 const int INF = 0x3f3f3f3f;

 const double Exp = 1e-;

 struct node

 {

     int x, y, w;

 };

 bool cmp (node a, node b)

 {

     return a.w < b.w;

 }

 node stu[maxn];

 int v, e, father[maxn], path[maxn];

 void init ()

 {

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

         father[i] = i;

 }

 int find (int x)

 {

     if (father[x] != x)

         father[x] = find(father[x]);

     return father[x];

 }

 int kruskal ()

 {

     int i, j, num = ;

     for (i=,j=; i<e; i++)

     {

         int px = find (stu[i].x);

         int py = find (stu[i].y);

         if (px != py)

         {

             num += stu[i].w;

             path[j++] = i;

             father[px] = py;

         }

     }

     int ans = ;

     for (i=; i<=v; i++)

         if (father[i] == i)

             ans ++;

     if (ans == )

         return num;

     return INF;

 }

 int smst (int x)

 {

     int i, num = ;

     for (i=; i<e; i++)

     {

         int px = find(stu[i].x);

         int py = find(stu[i].y);

         if (px != py && i != x)

         {

             num += stu[i].w;

             father[px] = py;

         }

     }

     int ans = ;

     for (i=; i<=v; i++)

         if (father[i] == i)

             ans ++;

     if (ans == )

         return num;

     return INF;

 }

 int main ()

 {

     int t, l = ;

     scanf ("%d", &t);

     while (t --)

     {

         scanf ("%d %d", &v, &e);

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

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

         sort (stu, stu+e, cmp);

         int num1 , num2;

         num1 = num2 = INF;

         init ();

         num1 = kruskal();

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

         {

             init ();

             num2 = min (num2, smst(path[i]));

         }

         if (num1 == INF)

             printf ("Case #%d : No way\n", l++);

         else if (num2 == INF)

             printf ("Case #%d : No second way\n", l++);

         else

             printf ("Case #%d : %d\n", l++, num2);

     }

     return ;

 }

巴特西

UVA 10462 Is There A Second Way Left? (次小生成树+kruskal)

最新文章

热门文章