Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- using namespace std;
- const int inf = 100;
- struct kletka
- {
- };
- class Graph
- {
- public:
- int n, count = 0, happy_koeff = 0, current_man = 0, *engagement, *index_free, **man, **woman;
- Graph(int x, int **arr, int **ar)
- {
- n = x;
- man = arr;
- woman = ar;
- engagement = new int[n];
- index_free = new int[n];
- for (int i = 0; i < n; i++)
- {
- engagement[i] = -1;
- index_free[i] = 0;
- }
- }
- void poisk();
- int make_offer(int current_man);
- void result();
- };
- void Graph::poisk()
- {
- int x;
- while (count != n)
- {
- x = make_offer(current_man);
- if (x == 0)
- {
- count++;
- current_man = count;
- }
- else current_man = x;
- }
- result();
- }
- int Graph::make_offer(int current_man)
- {
- int offer, x = -1;
- offer = man[current_man][index_free[current_man]] - 1;
- if (engagement[offer] == -1)
- {
- engagement[offer] = current_man;
- x = 0;
- }
- else
- {
- for (int i = 0; i < n; i++)
- if (woman[offer][i] == current_man+1)
- {
- for (int j = 0; j < n; j++)
- if (woman[offer][j] == engagement[offer]+1)
- {
- x = j;
- break;
- }
- if (x < i)
- {
- x = engagement[offer];
- index_free[x]++;
- engagement[offer] = current_man;
- }
- else x = -1;
- break;
- }
- }
- if (x == -1)
- {
- x = current_man;
- index_free[current_man]++;
- }
- return x;
- }
- void Graph::result()
- {
- for (int i = 0; i < n; i++)
- cout << engagement[i] + 1 << " ";
- cout << endl;
- for (int i = 0; i < n; i++)
- cout << index_free[i] + 1 << " ";
- }
- int main()
- {
- int n;
- cin >> n;
- int **man = new int*[n];
- int **woman = new int*[n];
- for (int i = 0; i < n; i++)
- {
- man[i] = new int[n];
- woman[i] = new int[n];
- }
- for (int i = 0; i < n; i++)
- for (int j = 0; j < n; j++)
- cin >> man[i][j];
- for (int i = 0; i < n; i++)
- for (int j = 0; j < n; j++)
- cin >> woman[i][j];
- Graph object(n, man, woman);
- object.poisk();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement