allia

марьяж

Jan 12th, 2021
700
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. const int inf = 100;
  6.  
  7.  struct kletka
  8. {
  9.  
  10. };
  11.  
  12. class Graph
  13. {
  14. public:
  15.     int n, count = 0, happy_koeff = 0, current_man = 0, *engagement, *index_free, **man, **woman;
  16.     Graph(int x, int **arr, int **ar)
  17.     {
  18.        n = x;
  19.        man = arr;
  20.        woman = ar;
  21.        engagement = new int[n];
  22.        index_free = new int[n];
  23.  
  24.        for (int i = 0; i < n; i++)
  25.         {
  26.           engagement[i] = -1;
  27.           index_free[i] = 0;
  28.         }
  29.     }
  30.     void poisk();
  31.     int make_offer(int current_man);
  32.     void result();
  33. };
  34.  
  35. void Graph::poisk()
  36. {
  37.   int x;
  38.  
  39.     while (count != n)
  40.   {
  41.         x = make_offer(current_man);
  42.         if (x == 0)
  43.     {
  44.             count++;
  45.       current_man = count;
  46.         }
  47.         else current_man = x;  
  48.     }
  49.   result();
  50. }
  51.  
  52. int Graph::make_offer(int current_man)
  53. {
  54.   int offer, x = -1;
  55.        
  56.     offer = man[current_man][index_free[current_man]] - 1;
  57.  
  58.         if (engagement[offer] == -1)
  59.     {
  60.             engagement[offer] = current_man;
  61.             x = 0;
  62.         }
  63.         else
  64.     {
  65.             for (int i = 0; i < n; i++)
  66.                 if (woman[offer][i] == current_man+1)
  67.                     {
  68.             for (int j = 0; j < n; j++)
  69.              if (woman[offer][j] == engagement[offer]+1)
  70.               {
  71.                 x = j;
  72.                 break;
  73.               }
  74.              if (x < i)
  75.              {
  76.                x = engagement[offer];
  77.                index_free[x]++;
  78.                engagement[offer] = current_man;
  79.              }
  80.              else x = -1;
  81.              break;
  82.           }
  83.      }
  84.      if (x == -1)
  85.       {
  86.         x = current_man;
  87.         index_free[current_man]++;
  88.       }
  89.  
  90.   return x;
  91. }
  92.  
  93. void Graph::result()
  94. {
  95.   for (int i = 0; i < n; i++)
  96.    cout << engagement[i] + 1 << " ";
  97.    cout << endl;
  98.   for (int i = 0; i < n; i++)
  99.    cout << index_free[i] + 1 << " ";
  100. }
  101.  
  102. int main()
  103. {
  104.     int n;
  105.     cin >> n;
  106.     int **man = new int*[n];
  107.     int **woman = new int*[n];
  108.    
  109.     for (int i = 0; i < n; i++)
  110.      {
  111.        man[i] = new int[n];
  112.        woman[i] = new int[n];
  113.      }
  114.  
  115.     for (int i = 0; i < n; i++)
  116.      for (int j = 0; j < n; j++)
  117.       cin >> man[i][j];
  118.    
  119.     for (int i = 0; i < n; i++)
  120.      for (int j = 0; j < n; j++)
  121.       cin >> woman[i][j];
  122.    
  123.     Graph object(n, man, woman);
  124.     object.poisk();
  125. }
RAW Paste Data