Advertisement
rotti321

Kruskal

Apr 2nd, 2022
23
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #define INFINIT 1000000000
  4. using namespace std;
  5.  
  6. ifstream fin("kruskal.in");
  7. ofstream fout("kruskal.out");
  8.  
  9. struct muchie
  10. {
  11. int i,j,cost;
  12. };
  13.  
  14. int n, m, t[105];
  15.  
  16. muchie x[5000];
  17. int v[5000];
  18.  
  19. int main()
  20. {
  21. fin >> n >> m;
  22.  
  23. for(int i = 0 ; i < m ; ++i)
  24. fin >> x[i].i >> x[i].j >> x[i].cost;
  25.  
  26. for(int i = 0 ; i < m - 1; i ++)
  27. for(int j = i + 1 ; j < m ; ++j)
  28. if(x[i].cost > x[j].cost)
  29. {
  30. muchie aux = x[i];
  31. x[i] = x[j];
  32. x[j] = aux;
  33. }
  34. for(int i =1 ; i <= n ; ++i)
  35. t[i] = i;
  36. int S = 0;
  37. for(int i = 0 ; i < m ; i ++)
  38. if(t[x[i].i] != t[x[i].j])
  39. {
  40. v[i] = 1;
  41. S += x[i].cost;
  42. int ai = t[x[i].i], aj = t[x[i].j];
  43. for(int j =1 ; j <= n ; ++j)
  44. if(t[j] == aj)
  45. t[j] = ai;
  46. }
  47. fout << S << " ";
  48. for(int i = 0 ; i < m ; ++i)
  49. if(v[i] == 1)
  50. fout << x[i].i << " " << x[i].j << " ";
  51. return 0;
  52. }
Advertisement
RAW Paste Data Copied
Advertisement