最小生成树之Kruskal

时间：2023-04-04 20:12:02

模板题，学习一下最小生成树的Kruskal算法

对于一个连通网（连通带权图，假定每条边上的权均为大于零的实数）来说，每棵树的权（即树中所有边的权值总和）也可能不同

具有权最小的生成树称为最小生成树

生成树：

  • 无向连通图的边的集合
  • 无回路
  • 连接所有的点

最小：

  • 所有边的权值之和最小

n个顶点的树有n-1条边

时间复杂度：O(ElogE)

对于稀疏图来说

按所给的边的权值从小到大排序，如果该边不与已经选的边形成环就选择它

这里用并查集来实现

第i条边的端点放在u、v数组中，权值保存在w中

这里用的是间接排序，也就是排的是每条边的序号，放在rank数组中

下面是两道模板题：

HDU 1863 畅通工程

 //#define LOCAL

 #include <algorithm>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int maxn = ;

 int u[maxn], v[maxn], w[maxn], parent[maxn], rank[maxn];

 int m, n;

 bool cmp(const int i, const int j)

 {

     return (w[i] < w[j]);

 }

 int GetParent(int a)

 {

     return parent[a] == a ? a : parent[a] = GetParent(parent[a]);

 }

 int kruskal(void)

 {

     int cnt = , weight = ;

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

     {

         int edge = rank[i];

         int x = GetParent(u[edge]);

         int y = GetParent(v[edge]);

         if(x != y)

         {

             weight += w[edge];

             ++cnt;

             parent[x] = y;

         }

     }

     if(cnt < n - )    weight = ;

     return weight;

 }

 int main(void)

 {

     #ifdef LOCAL

         freopen("1863in.txt", "r", stdin);

     #endif

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

     {

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

             scanf("%d%d%d", &u[i], &v[i], &w[i]);

         for(int i = ; i < n; ++i)    parent[i] = i;

         for(int i = ; i < m; ++i)    rank[i] = i;

         sort(rank, rank + m, cmp);

         int ans = kruskal();

         if(ans)

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

         else

             printf("?\n");

     }

     return ;

 }

代码君一

POJ 1861 Network

感觉这道题略坑啊，它并没有说是多组输入啊，而且输出的第一个数是边里面的最大权值啊，数组开了1000多开小了啊，还有各种小错误啊。Orz

好吧，这些都是我的错误，上来就套模板，没有好好读题

 //#define LOCAL

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 int v[maxn], u[maxn], r[maxn], p[maxn], w[maxn], path[maxn];

 int n, m, cnt, ans;

 int Find(int a)

 {

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

 }

 bool cmp(const int i, const int j)

 {

     return (w[i] < w[j]);

 }

 void Kruskal(void)

 {

     cnt = , ans = -;

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

     {

         int edge = r[i];

         int x = Find(u[edge]);

         int y = Find(v[edge]);

         if(x != y)

         {

             ans = max(ans, w[edge]);

             p[x] = y;

             path[cnt++] = i;

         }

     }

 }

 void OutPut(void)

 {

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

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

         printf("%d %d\n", u[r[path[i]]], v[r[path[i]]]);

 }

 int main(void)

 {

     #ifdef LOCAL

         freopen("1861in.txt", "r", stdin);

     #endif

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

     {

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

         scanf("%d%d%d", &u[i], &v[i], &w[i]);

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

         for(int i = ; i < m; ++i)    r[i] = i;

         sort(r, r + m, cmp);

         Kruskal();

         OutPut();

     }

     return ;

 }

代码君二

POJ 2560 Freckles

题意：给出n个点的坐标，求最小生成树的长度。奇怪的是G++没过，C++却过了

 //#define LOCAL

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 using namespace std;

 const int maxn =  + ;

 struct Node

 {

     double x, y;

 }pos[maxn];

 int u[maxn], v[maxn], r[maxn], p[maxn];

 double w[maxn];

 bool cmp(const int i, const int j)

 {

     return (w[i] < w[j]);

 }

 int Find(int a)

 {

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

 }

 double Kruskal(int cnt)

 {

     double ans = 0.0;

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

     {

         int edge = r[i];

         int x = Find(u[edge]);

         int y = Find(v[edge]);

         if(x != y)

         {

             ans += w[edge];

             p[x] = y;

         }

     }

     return ans;

 }

 int main(void)

 {

     #ifdef LOCAL

         freopen("2560in.txt", "r", stdin);

     #endif

     int n, cnt;

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

     {

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

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

             scanf("%lf %lf", &pos[i].x, &pos[i].y);

         cnt = ;

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

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

             {

                 u[cnt] = i;

                 v[cnt] = j;

                 r[cnt] = cnt;

                 w[cnt++] = sqrt((pos[i].x-pos[j].x)*(pos[i].x-pos[j].x) + (pos[i].y-pos[j].y)*(pos[i].y-pos[j].y));

             }

         sort(r, r + cnt, cmp);

         printf("%.2lf\n", Kruskal(cnt));

     }

     return ;

 }

代码君三

相关文章