Advertisement
PopaLepo

Retea de cost minim intre orase

Jan 22nd, 2017
179
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.54 KB | None | 0 0
  1. /* Trebuie sa se construiasca o retea de autostrazi care sa lege cele mai importante orase din tara. Fiecare tronson de autostrada care leaga doua oras e are un cost de construire. Sa se determine reteaua de autostrazi astfel incat toate orasele sa fie legate prin autostrazi si costul construirii ei sa fie minim. */
  2.  
  3. #include <iostream>
  4. #include <string.h>
  5. #include <fstream>
  6.  
  7. using namespace std;
  8. ifstream f("graf.txt");
  9. int a[100][100],n,m,c[100][100],t[100],s[100],p[100],v1,v2,sum;
  10. char o[100][30],nume[30];
  11.  
  12. void citire()
  13. {
  14. int p1,p2,z;
  15. char x[100],y[100];
  16. f>>n>>m;
  17.  
  18. for(int i=1;i<=m;i++)
  19. for(int j=1;j<=m;j++)
  20. c[i][j]=32000;
  21.  
  22. for(int i=1;i<=n;i++)
  23. f>>o[i];
  24. for(int i=1;i<=m;i++)
  25. {f>>x>>y>>z;
  26. for(int j=1;j<=n;j++)
  27. {if(strcmp(o[j],x)==0)
  28. p1=j;
  29. if(strcmp(o[j],y)==0)
  30. p2=j;}
  31.  
  32. c[p1][p2]=c[p2][p1]=z;
  33. }}
  34.  
  35. void Prim()
  36. {
  37. int f;
  38. cout<<"Localitatea din care porniti :";
  39. cin>>nume;
  40. for(int i=1;i<=n;i++)
  41. if(strcmp(nume,o[i])==1)
  42. f=i;
  43. s[f]=1;
  44. for(int k=1;k<=n-1;k++)
  45. {
  46. int minn=32000;
  47. for(int i=1;i<=n;i++)
  48. for(int j=1;j<=n;j++)
  49.  
  50. if(c[i][j]<minn && s[i]==1 && s[j]==0)
  51. {
  52. minn=c[i][j];
  53. v1=i;
  54. v2=j;
  55. }
  56. t[v2]=v1;
  57. s[v2]=1;
  58. p[v2]=c[v1][v2];
  59. }
  60. }
  61.  
  62. void afis()
  63. {
  64. for(int i=1;i<=n;i++)
  65. if(t[i]!=0)
  66. cout<<o[t[i]]<<" "<<o[i]<<endl;
  67. cout<<"Costul total: ";
  68. for(int i=1;i<=n;i++)
  69. sum+=p[i];
  70. cout<<sum;
  71. }
  72.  
  73. int main()
  74. {
  75. citire();
  76. Prim();
  77. afis();
  78. return 0;}
  79.  
  80.  
  81. graf.txt :
  82.  
  83. 5 7
  84. Iasi Deva Cluj Sibiu Arad
  85.  
  86. Iasi Deva 10
  87. Deva Cluj 20
  88. Sibiu Arad 30
  89. Arad Iasi 50
  90. Cluj Arad 60
  91. Deva Sibiu 45
  92. Iasi Cluj 5
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement