SHARE
TWEET

123

a guest Jan 22nd, 2020 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define N 1001
  3. using namespace std;
  4. ifstream fin("kruskal.in");
  5. ofstream fout("kruskal.out");
  6. struct muchie
  7. {
  8.   int x,y,c;
  9. };
  10. struct muc
  11. {
  12.     int x,y;
  13. };
  14. muchie a[N];
  15. muc v[N];
  16. int t[N];
  17. int n,m,k;
  18. void Read()
  19. {
  20.     fin>>n>>m;
  21.     for(int i=1;i<=m;i++)
  22.     {
  23.         fin>>a[i].x>>a[i].y>>a[i].c;
  24.     }
  25. }
  26. int CMP(muchie A, muchie B)
  27. {
  28.     return A.c<B.c;
  29. }
  30. void Union(int x, int y)
  31. {
  32.     t[y]=x;
  33. }
  34. int Find(int x)
  35. {
  36.     int y,rad;
  37.     rad=x;
  38.     while(t[rad]!=0)
  39.         rad=t[rad];
  40.     while(x!=rad)
  41.     {
  42.         y=t[x];
  43.         t[x]=rad;
  44.         x=y;
  45.     }
  46.     return rad;
  47. }
  48. void Kruskal()
  49. {
  50.     int p,q,i,costmin=0;
  51.     sort(a+1,a+m+1,CMP);
  52.     for(i=1;i<=m;i++)
  53.     {
  54.         p=Find(a[i].x);
  55.         q=Find(a[i].y);
  56.         if(p!=q)
  57.         {
  58.             v[++k].x=a[i].x;
  59.             v[k].y=a[i].y;
  60.             costmin+=a[i].c;
  61.             Union(p,q);
  62.         }
  63.     }
  64.     fout<<costmin<<"\n";
  65.     for(int i=1;i<=k;i++)
  66.         fout<<v[i].x<<" "<<v[i].y<<"\n";
  67. }
  68. int main()
  69. {
  70.     Read();
  71.     Kruskal();
  72.     return 0;
  73. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top