Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- struct Osoba{
- int ilosc;
- int *rowery;
- int wartosc;
- bool skojarzone;
- bool rozpatrzone;
- };
- Osoba *osoby;
- int * rowery;
- int *skojarzoneRowery;
- bool *skojarzoneTab;
- bool *rozpatrzoneTab;
- int liczbaOsob, liczbaRowerow;
- int skojarzoneIlosc = 0;
- void Pobierz() {
- //zczytywanie
- scanf("%d", &liczbaOsob);
- scanf("%d", &liczbaRowerow);
- //alokacja dynamiczna
- osoby = new Osoba[liczbaOsob];
- rowery = new int[liczbaRowerow];
- skojarzoneRowery = new int[liczbaRowerow];
- skojarzoneTab = new bool[liczbaRowerow];
- rozpatrzoneTab = new bool[liczbaRowerow];
- //inicjalizowanie starowe rowerow
- for (int i = 0; i < liczbaRowerow; i++)
- {
- skojarzoneTab[i] = false;
- rozpatrzoneTab[i] = false;
- skojarzoneRowery[i] = NULL;
- }
- for (int i = 0; i < liczbaOsob; i++) {
- //inicjalizowanie startowe osob
- osoby[i].skojarzone = false;
- osoby[i].rozpatrzone = false;
- osoby[i].wartosc = -1;
- //zczytywanie preferowanych rowerow
- scanf("%d", &osoby[i].ilosc);
- int ilosc = osoby[i].ilosc;
- osoby[i].rowery = new int[ilosc];
- osoby[i].rowery = new int[ilosc];
- for (int j = 0; j < ilosc; j++) {
- scanf("%d", &osoby[i].rowery[j]);
- }
- }
- }
- void Skojarz() {
- for (int i = 0; i < liczbaOsob; i++) {
- int wsk = 0;
- while (wsk < osoby[i].ilosc) {
- int j = osoby[i].rowery[wsk];
- if (skojarzoneTab[j-1] == false) {
- skojarzoneTab[j-1] = true;
- skojarzoneRowery[j-1] = i +1;
- osoby[i].skojarzone = true;
- skojarzoneIlosc++;
- //cout << "*";
- wsk = osoby[i].ilosc;
- }
- else
- wsk++;
- }
- }
- }
- void BFS() {
- int *kolejka = new int[liczbaOsob];
- int iloscNaKolejce=0;
- int wsk=0;
- for (int i = 0; i < liczbaOsob; i++) {
- if (osoby[i].skojarzone == false)
- {
- kolejka[ iloscNaKolejce++] = i+1;
- osoby[i].wartosc = 0;
- }
- }
- while(wsk<iloscNaKolejce){
- int osobaPierwsza = kolejka[wsk]-1;
- for (int i = 0; i < osoby[osobaPierwsza].ilosc; i++) {
- int ro = osoby[osobaPierwsza].rowery[i]-1;
- if (skojarzoneTab[ro] == true && osoby[skojarzoneRowery[ro]-1].wartosc<0){//osoby[skojarzoneRowery[osoby[osobaPierwsza].rowery[i]]].wartosc == -1) {
- osoby[skojarzoneRowery[ro]-1].wartosc = osoby[osobaPierwsza].wartosc + 1;
- kolejka[iloscNaKolejce++] = skojarzoneRowery[ro];
- }
- }
- wsk++;
- }
- delete[] kolejka;
- }
- bool DFS(int x) {
- osoby[x].rozpatrzone = true;
- for(int i=0;i<osoby[x].ilosc;i++){
- if (skojarzoneTab[osoby[x].rowery[i]-1] == false) {
- osoby[x].skojarzone = true;
- skojarzoneTab[osoby[x].rowery[i]-1] = true;
- skojarzoneRowery[osoby[x].rowery[i]-1] = x + 1;
- return true;
- }
- int os = skojarzoneRowery[osoby[x].rowery[i]-1]-1;
- if (osoby[os].rozpatrzone == false && osoby[os].wartosc == osoby[x].wartosc+1 ) {
- if (DFS(os)) {
- osoby[x].skojarzone = true;
- skojarzoneTab[osoby[x].rowery[i]-1] = true;
- skojarzoneRowery[osoby[x].rowery[i]-1]= x+1;
- skojarzoneIlosc++;
- return true;
- }
- }
- }
- return false;
- }
- int main()
- {
- Pobierz();
- Skojarz();
- bool dfs=true;
- for (int j = 0; j < 10; j++) {
- for (int i = 0; i < liczbaOsob; i++) {
- osoby[i].wartosc = -1;
- }
- BFS();
- for (int i = 0; i < liczbaOsob; i++) {
- osoby[i].rozpatrzone = false;
- if (osoby[i].skojarzone == false) {
- dfs = DFS(i);
- }
- }
- }
- int skojarzone=0;
- for (int i = 0; i < liczbaOsob; i++){
- if (osoby[i].skojarzone == true)
- skojarzone++;
- }
- cout << skojarzone;
- system("pause");
- /*osoba[wsk] = v;
- rower[wsk] = last[u];
- last[u] = wsk++;*/
- delete[] osoby;
- delete[]rowery;
- delete[]skojarzoneRowery;
- delete[] skojarzoneTab;
- delete[] rozpatrzoneTab;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement