Code666 (代码贴、代码片段)

[C++] 最小生成树（Kruskal） →→→→→进入此内容的聊天室

来自 , 2020-11-19, 写在 C++, 查看 106 次.
URL http://www.code666.cn/view/8c249675
  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int maxn = 5005;
  8.  
  9. struct Edge
  10. {
  11.         int u;
  12.         int v;
  13.         int val;
  14.         bool operator < (const Edge &b)const
  15.         {
  16.                 return val < b.val;
  17.         }
  18. }edge[maxn];
  19.  
  20. int n;
  21. int father[105];
  22.  
  23. int find(int x)
  24. {
  25.         int r = x;
  26.         while(r != father[r])
  27.                 r = father[r];
  28.         int i = x,t;
  29.         while(i != r)
  30.         {
  31.                 t = father[i];
  32.                 father[i] = r;
  33.                 i = t;
  34.         }
  35.         return r;
  36. }
  37.  
  38. void mix(int x,int y)
  39. {
  40.         int fx = find(x);
  41.         int fy = find(y);
  42.         if(fx != fy)
  43.                 father[fx] = fy;
  44. }
  45.  
  46. int kruskal(int e)
  47. {
  48.         int ans = 0;
  49.         int cnt = 0;
  50.         for(int i = 0;i < e;i++)
  51.         {
  52.                 if(find(edge[i].u) != find(edge[i].v))
  53.                 {
  54.                         cnt++;
  55.                         mix(edge[i].u,edge[i].v);
  56.                         ans += edge[i].val;
  57.                 }
  58.                 if(cnt == n-1)
  59.                         break;
  60.         }
  61.         return ans;
  62. }
  63. int main()
  64. {
  65.  
  66.     while(scanf("%d",&n) != EOF && n)
  67.     {
  68.         for(int i = 1;i <= n;i++)
  69.                 father[i] = i;
  70.         int e = n*(n-1)/2;
  71.         for(int i = 0;i < e;i++)
  72.         {
  73.                 int is;
  74.                 scanf("%d%d%d%d",&edge[i].u,&edge[i].v,&edge[i].val,&is);
  75.                 if(is)
  76.                         edge[i].val = 0;
  77.             }
  78.             sort(edge,edge+e);
  79.  
  80.             printf("%d\n",kruskal(e));
  81.     }
  82.     return 0;
  83. }
  84.  

回复 "最小生成树（Kruskal）"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666