Advertisement
Guest User

Untitled

a guest
Mar 31st, 2020
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.37 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. using namespace std;
  4.  
  5. ifstream f("zapada.in");
  6. ofstream g("zapada.out");
  7.  
  8. const int NMax=105;
  9. const int MMax=100000;
  10. int n, m;
  11. int numar_arbore[NMax];
  12. int cost_total;
  13. int k;
  14. struct muchie
  15. {
  16. int nod1, nod2;
  17. int cost;
  18. }v[MMax];
  19.  
  20. void citire()
  21. {
  22. f>>n>>m;
  23.  
  24. for(int i=1; i<=m; i++)
  25. f>>v[i].nod1>>v[i].nod2>>v[i].cost;
  26.  
  27.  
  28. int drumuri, poz;
  29. f>>drumuri;
  30. for(int i=1; i<=drumuri; i++)
  31. {
  32. f>>poz;
  33. muchie aux=v[++k];
  34. v[k]=v[poz];
  35. v[poz]=aux;
  36. }
  37. }
  38.  
  39. void sortare(int pozitie)
  40. {
  41. int ok;
  42. do
  43. {
  44. ok=1;
  45. for(int i=pozitie; i<m; i++)
  46. {
  47. int c1=v[i].cost;
  48. int c2=v[i+1].cost;
  49. if(c1>c2)
  50. {
  51. ok=0;
  52. muchie aux=v[i];
  53. v[i]=v[i+1];
  54. v[i+1]=aux;
  55. }
  56. }
  57. }while(ok==0);
  58. }
  59.  
  60.  
  61. void schimbare_numar_arbore(int a, int b)
  62. {
  63. for(int i=1; i<=n; i++)
  64. if(numar_arbore[i]==b)
  65. numar_arbore[i]=a;
  66. }
  67.  
  68. void Kruskal()
  69. {
  70. sortare(k+1);
  71.  
  72. for(int i=1; i<=n; i++)
  73. numar_arbore[i]=i;
  74.  
  75. for(int i=1; i<=n; i++)
  76. {
  77. int nod1=v[i].nod1;
  78. int nod2=v[i].nod2;
  79. if(numar_arbore[nod1]!=numar_arbore[nod2])
  80. {
  81. cost_total+=v[i].cost;
  82. schimbare_numar_arbore(numar_arbore[nod1], numar_arbore[nod2]);
  83. }
  84. }
  85. }
  86.  
  87. int main()
  88. {
  89. citire();
  90. Kruskal();
  91. g<<cost_total;
  92. return 0;
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement