Advertisement
Guest User

Untitled

a guest
Dec 16th, 2017
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.77 KB | None | 0 0
  1. #include <iostream>
  2. #include <list>
  3. #include <stack>
  4. #include <fstream>
  5. #include <cstdlib>
  6. #include <string>
  7.  
  8. using namespace std;
  9. fstream plikin;
  10. class Graf
  11. {
  12. int ilosc_wierz;
  13. list<int> *LI;
  14.  
  15.  
  16. void wypelnij_czas(int v, bool visited[], stack<int> &Stack)
  17. {
  18. visited[v] = true;
  19. list<int>::iterator i;
  20. for(i = LI[v].begin(); i != LI[v].end(); ++i)
  21. if(!visited[*i])
  22. wypelnij_czas(*i, visited, Stack);
  23. Stack.push(v);
  24. }
  25.  
  26. void WB22(int v, bool visited[])
  27. {
  28.  
  29. visited[v] = true;
  30.  
  31.  
  32. list<int>::iterator i;
  33. for (i = LI[v].begin(); i != LI[v].end(); ++i)
  34. if (!visited[*i])
  35. WB22(*i, visited);
  36. }
  37.  
  38. void WB(int v, bool visited[])
  39. {
  40.  
  41. visited[v] = true;
  42. plikin << v << " ";
  43.  
  44. list<int>::iterator i;
  45. for (i = LI[v].begin(); i != LI[v].end(); ++i)
  46. if (!visited[*i])
  47. WB(*i, visited);
  48. }
  49. public:
  50. Graf(int V)
  51. {
  52. ilosc_wierz = V;
  53. LI = new list<int>[V];
  54. }
  55. void dodaj_krawedz(int v, int w)
  56. {
  57. LI[v].push_back(w);
  58. }
  59. Graf transponuj()
  60. {
  61. Graf g(ilosc_wierz);
  62. for (int v = 0; v < ilosc_wierz; v++)
  63. {
  64. list<int>::iterator i;
  65. for(i = LI[v].begin(); i != LI[v].end(); ++i)
  66. {
  67. g.LI[*i].push_back(v);
  68. }
  69. }
  70. return g;
  71. }
  72.  
  73. void printSCCs(int w)
  74. {
  75. stack<int> Stack;
  76.  
  77. bool *visited = new bool[ilosc_wierz];
  78. for(int i = 1; i < ilosc_wierz; i++)
  79. visited[i] = false;
  80.  
  81. for(int i = 1; i < ilosc_wierz; i++)
  82. if(visited[i] == false)
  83. wypelnij_czas(i, visited, Stack);
  84.  
  85.  
  86.  
  87. Graf gr = transponuj();
  88.  
  89. for(int i = 1; i < ilosc_wierz; i++)
  90. visited[i] = false;
  91.  
  92.  
  93. while (Stack.empty() == false)
  94. {
  95. int v = Stack.top();
  96. Stack.pop();
  97.  
  98. if (visited[v] == false)
  99. {
  100. if(v==w){ gr.WB(v, visited); }
  101. else{ gr.WB22(v, visited); }
  102. }
  103. }
  104. plikin<<endl;
  105. }
  106. };
  107.  
  108.  
  109. int main()
  110. {
  111.  
  112. fstream plikout;
  113.  
  114. plikout.open("plikout.txt", std::ios::in);
  115. plikin.open("plikin.txt", std::ios::out);
  116. int n,m,k,t;
  117. double CHF;
  118. double EUR;
  119. double macierz[11][11];
  120. int i=1;
  121. int j=1;
  122. if(plikout)
  123. {
  124. plikout >> n >> m >> CHF >>EUR >> k >> t;
  125. while(!plikout.eof())
  126. {
  127.  
  128. for(int z=1;z<11;z++)
  129. {
  130. plikout >> macierz[i][j];
  131. j++;
  132. }
  133. j=1;i++;
  134. }
  135.  
  136. }
  137.  
  138. plikout.close();
  139. n+=1;
  140. Graf zadanie(n);
  141.  
  142. for(int i=1;i<11;i++)
  143. {
  144. for(int j=1;j<11;j++)
  145. {
  146. if(m*(1-macierz[i][j]) > CHF - EUR) zadanie.dodaj_krawedz(i,j);
  147. }
  148.  
  149. }
  150.  
  151.  
  152. zadanie.printSCCs(k);
  153. zadanie.printSCCs(t);
  154.  
  155. return 0;
  156. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement