Advertisement
dariahinz

Untitled

Jun 3rd, 2017
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.74 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. struct Osoba{
  5. int ilosc;
  6. int *rowery;
  7. int wartosc;
  8. bool skojarzone;
  9. bool rozpatrzone;
  10. };
  11.  
  12. Osoba *osoby;
  13. int * rowery;
  14. int *skojarzoneRowery;
  15. bool *skojarzoneTab;
  16. bool *rozpatrzoneTab;
  17. int liczbaOsob, liczbaRowerow;
  18. int skojarzoneIlosc = 0;
  19.  
  20. void Pobierz() {
  21. //zczytywanie
  22. scanf("%d", &liczbaOsob);
  23. scanf("%d", &liczbaRowerow);
  24. //alokacja dynamiczna
  25. osoby = new Osoba[liczbaOsob];
  26. rowery = new int[liczbaRowerow];
  27. skojarzoneRowery = new int[liczbaRowerow];
  28. skojarzoneTab = new bool[liczbaRowerow];
  29. rozpatrzoneTab = new bool[liczbaRowerow];
  30. //inicjalizowanie starowe rowerow
  31. for (int i = 0; i < liczbaRowerow; i++)
  32. {
  33. skojarzoneTab[i] = false;
  34. rozpatrzoneTab[i] = false;
  35. skojarzoneRowery[i] = NULL;
  36. }
  37.  
  38. for (int i = 0; i < liczbaOsob; i++) {
  39. //inicjalizowanie startowe osob
  40. osoby[i].skojarzone = false;
  41. osoby[i].rozpatrzone = false;
  42. osoby[i].wartosc = -1;
  43. //zczytywanie preferowanych rowerow
  44. scanf("%d", &osoby[i].ilosc);
  45. int ilosc = osoby[i].ilosc;
  46. osoby[i].rowery = new int[ilosc];
  47. osoby[i].rowery = new int[ilosc];
  48. for (int j = 0; j < ilosc; j++) {
  49. scanf("%d", &osoby[i].rowery[j]);
  50. }
  51. }
  52. }
  53. void Skojarz() {
  54.  
  55. for (int i = 0; i < liczbaOsob; i++) {
  56. int wsk = 0;
  57. while (wsk < osoby[i].ilosc) {
  58. int j = osoby[i].rowery[wsk];
  59. if (skojarzoneTab[j-1] == false) {
  60. skojarzoneTab[j-1] = true;
  61. skojarzoneRowery[j-1] = i +1;
  62. osoby[i].skojarzone = true;
  63. skojarzoneIlosc++;
  64. //cout << "*";
  65. wsk = osoby[i].ilosc;
  66.  
  67. }
  68. else
  69. wsk++;
  70. }
  71.  
  72. }
  73. }
  74.  
  75. void BFS() {
  76. int *kolejka = new int[liczbaOsob];
  77. int iloscNaKolejce=0;
  78. int wsk=0;
  79.  
  80. for (int i = 0; i < liczbaOsob; i++) {
  81. if (osoby[i].skojarzone == false)
  82. {
  83. kolejka[ iloscNaKolejce++] = i+1;
  84.  
  85. osoby[i].wartosc = 0;
  86. }
  87. }
  88. while(wsk<iloscNaKolejce){
  89.  
  90. int osobaPierwsza = kolejka[wsk]-1;
  91.  
  92. for (int i = 0; i < osoby[osobaPierwsza].ilosc; i++) {
  93.  
  94. int ro = osoby[osobaPierwsza].rowery[i]-1;
  95.  
  96. if (skojarzoneTab[ro] == true && osoby[skojarzoneRowery[ro]-1].wartosc<0){//osoby[skojarzoneRowery[osoby[osobaPierwsza].rowery[i]]].wartosc == -1) {
  97.  
  98. osoby[skojarzoneRowery[ro]-1].wartosc = osoby[osobaPierwsza].wartosc + 1;
  99.  
  100.  
  101. kolejka[iloscNaKolejce++] = skojarzoneRowery[ro];
  102.  
  103. }
  104. }
  105. wsk++;
  106.  
  107. }
  108.  
  109. delete[] kolejka;
  110. }
  111. bool DFS(int x) {
  112.  
  113. osoby[x].rozpatrzone = true;
  114.  
  115. for(int i=0;i<osoby[x].ilosc;i++){
  116.  
  117. if (skojarzoneTab[osoby[x].rowery[i]-1] == false) {
  118. osoby[x].skojarzone = true;
  119. skojarzoneTab[osoby[x].rowery[i]-1] = true;
  120. skojarzoneRowery[osoby[x].rowery[i]-1] = x + 1;
  121.  
  122. return true;
  123. }
  124.  
  125. int os = skojarzoneRowery[osoby[x].rowery[i]-1]-1;
  126.  
  127.  
  128. if (osoby[os].rozpatrzone == false && osoby[os].wartosc == osoby[x].wartosc+1 ) {
  129.  
  130. if (DFS(os)) {
  131. osoby[x].skojarzone = true;
  132. skojarzoneTab[osoby[x].rowery[i]-1] = true;
  133. skojarzoneRowery[osoby[x].rowery[i]-1]= x+1;
  134. skojarzoneIlosc++;
  135. return true;
  136. }
  137.  
  138.  
  139. }
  140. }
  141. return false;
  142.  
  143. }
  144.  
  145.  
  146. int main()
  147. {
  148. Pobierz();
  149. Skojarz();
  150. bool dfs=true;
  151. for (int j = 0; j < 10; j++) {
  152.  
  153. for (int i = 0; i < liczbaOsob; i++) {
  154.  
  155. osoby[i].wartosc = -1;
  156. }
  157. BFS();
  158. for (int i = 0; i < liczbaOsob; i++) {
  159. osoby[i].rozpatrzone = false;
  160. if (osoby[i].skojarzone == false) {
  161. dfs = DFS(i);
  162. }
  163.  
  164. }
  165.  
  166. }
  167.  
  168.  
  169. int skojarzone=0;
  170. for (int i = 0; i < liczbaOsob; i++){
  171. if (osoby[i].skojarzone == true)
  172. skojarzone++;
  173. }
  174. cout << skojarzone;
  175.  
  176.  
  177. system("pause");
  178. /*osoba[wsk] = v;
  179. rower[wsk] = last[u];
  180. last[u] = wsk++;*/
  181.  
  182. delete[] osoby;
  183. delete[]rowery;
  184. delete[]skojarzoneRowery;
  185. delete[] skojarzoneTab;
  186. delete[] rozpatrzoneTab;
  187.  
  188. return 0;
  189. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement