hdoj1102 Constructing Roads（Prime || Kruskal）

题目链接

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

题意

有n个村庄（编号1~n），给出n个村庄之间的距离，开始时n个村庄之间已经有了q条路，现在需要修一条路，这条路连接起所有的村庄，求在已经存在的路径的基础上，最少还需要修多长的路。

思路

普通最小生成树是从零开始构造一棵最小生成树，而这题开始时图中已经有了一些路径，那这些路就不需要被修了，所以将这些路的修理长度置为0，然后使用Prime算法或者Kruskal算法求解即可。

代码

Prime算法：

 #include <algorithm>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int INF = 0x7fffffff;

 const int N =  + ;

 int map[N][N];

 int dist[N];    //记录从起点到其余各点的长度，不断更新

 int n, q;

 void prime()

 {

     int min_edge, min_node;

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

         dist[i] = INF;

     int ans = ;

     int now = ;

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

     {

         min_edge = INF;

         dist[now] = -;

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

         {

             if (j != now && dist[j] >= )

             {

                 if (map[now][j] >= )    //注意是map[now][j]>=0,因为有些路已经修好了，初始化时令其长度为0

                     dist[j] = min(dist[j], map[now][j]);

                 if (dist[j] < min_edge)

                 {

                     min_edge = dist[j];    //min_edge存储与当前结点相连的最短的边

                     min_node = j;

                 }

             }

         }

         ans += min_edge;    //ans存储最小生成树的长度

         now = min_node;

     }

     printf("%d\n", ans);

 }

 int main()

 {

     //freopen("hdoj1102.txt", "r", stdin);

     while (scanf("%d", &n) == )

     {

         memset(map, , sizeof(map));

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

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

                 scanf("%d", &map[i][j]);

         scanf("%d", &q);

         int a, b;

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

         {

             scanf("%d%d", &a, &b);

             map[a][b] = map[b][a] = ;

         }

         prime();

     }

     return ;

 }

Kruskal算法：

 #include <algorithm>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 using namespace std;

 struct Edge

 {

     int a, b, dist;

     Edge() {}

     Edge(int a, int b, int d) :a(a), b(b), dist(d) {}

     bool operator < (Edge edge)    //将边按边长从短到长排序

     {

         return dist < edge.dist;

     }

 };

 const int N =  + ;

 int p[N];    //并查集使用

 int map[N][N];

 vector<Edge> v;

 int n, q;

 int find_root(int x)

 {

     if (p[x] == -)

         return x;

     else return find_root(p[x]);

 }

 void kruskal()

 {

     memset(p, -, sizeof(p));

     sort(v.begin(), v.end());

     int ans = ;

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

     {

         int ra = find_root(v[i].a);

         int rb = find_root(v[i].b);

         if (ra != rb)

         {

             ans += v[i].dist;

             p[ra] = rb;

         }

     }

     printf("%d\n", ans);

 }

 int main()

 {

     //freopen("hdoj1102.txt", "r", stdin);

     while (scanf("%d", &n) == )

     {

         v.clear();

         int t;

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

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

                 scanf("%d", &map[i][j]);

         scanf("%d", &q);

         int a, b;

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

         {

             scanf("%d%d", &a, &b);

             map[a][b] = map[b][a] = ;

         }

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

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

                 if (j > i)    v.push_back(Edge(i, j, map[i][j]));

         kruskal();

     }

     return ;

 }

注意点

这题是有多组输入数据的，如果只按一组输入数据处理的话会WA.