Advertisement
StoneHaos

6

Jan 23rd, 2022
679
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <limits.h>
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. const int n = 3, m = 5;
  9. int a[n], alfa[n];
  10. int b[m], beta[m];
  11. int x[n][m], c[n][m], delta[n][m];
  12. bool zapol[n][m];
  13. int rez;
  14.  
  15. int znaki[n][m];
  16. int kol_v_stroke[n];
  17. int kol_v_stolbce[m];
  18. bool zapol1[n][m];
  19. int sv_i, sv_j, i_tek, j_tek;
  20.  
  21. void Print() {
  22.     for (int i = 0; i < n; i++) {
  23.         printf("\n");
  24.         for (int j = 0; j < m; j++)
  25.             printf("%8d", x[i][j]);
  26.         printf("%8d", a[i]);
  27.     }
  28.     printf("\n");
  29.     for (int j = 0; j < m; j++)
  30.         printf("%8d", b[j]);
  31.     printf("\n");
  32. }
  33.  
  34. void ser_zap(int a[n], int b[m], int c[n][m]) {
  35.     for (int i = 0; i < n; i++) {
  36.         for (int j = 0; j < m; j++) {
  37.             if (b[j] != 0) {
  38.                 c[i][j] = min(a[i], b[j]);
  39.                 zapol[i][j] = true;
  40.                 a[i] = a[i] - c[i][j];
  41.                 b[j] = b[j] - c[i][j];
  42.                 if (a[i] == 0)
  43.                     break;
  44.             }
  45.         }
  46.     }
  47. }
  48.  
  49. void Potencial() {
  50.     for (int i = 0; i < n; i++)
  51.         alfa[i] = -INT_MAX;
  52.     for (int j = 0; j < m; j++)
  53.         beta[j] = -INT_MAX;
  54.     alfa[0] = 0;
  55.     bool f;
  56.  
  57.     do {
  58.         for (int i = 0; i < n; i++) {
  59.             for (int j = 0; j < m; j++) {
  60.                 if (zapol[i][j]) {
  61.                     if ((alfa[i] == -INT_MAX) && (beta[j] != -INT_MAX))
  62.                         alfa[i] = c[i][j] - beta[j];
  63.                     else
  64.                         if ((alfa[i] != -INT_MAX) && (beta[j] == -INT_MAX))
  65.                             beta[j] = c[i][j] - alfa[i];
  66.                 }
  67.             }
  68.         }
  69.         f = false;
  70.         for (int i = 0; i < n; i++)
  71.             if (alfa[i] == -INT_MAX)
  72.                 f = true;
  73.         for (int j = 0; j < m; j++)
  74.             if (beta[j] == -INT_MAX)
  75.                 f = true;
  76.     } while (f);
  77. }
  78.  
  79. void Ozenka() {
  80.     for (int i = 0; i < n; i++) {
  81.         for (int j = 0; j < m; j++) {
  82.             if (!(zapol[i][j]))
  83.                 delta[i][j] = beta[j] + alfa[i] - c[i][j];
  84.             else
  85.                 delta[i][j] = 0;
  86.         }
  87.     }
  88. }
  89.  
  90. bool optim() {
  91.     bool f = true;
  92.     for (int i = 0; i < n; i++) {
  93.         for (int j = 0; j < m; j++)
  94.             if (!(zapol[i][j]) && (delta[i][j] > 0))
  95.                 f = false;
  96.     }
  97.     return f;
  98. }
  99.  
  100. void Init_cicl() {
  101.  
  102.     for (int i = 0; i < n; ++i)
  103.         for (int j = 0; j < m; ++j) znaki[i][j] = 0;
  104.  
  105.     for (int i = 0; i < n; ++i)
  106.         kol_v_stroke[i] = 0;
  107.     for (int j = 0; j < m; ++j)
  108.         kol_v_stolbce[j] = 0;
  109.     for (int i = 0; i < n; ++i) {
  110.         for (int j = 0; j < m; ++j) {
  111.             if (zapol1[i][j]) {
  112.                 kol_v_stroke[i]++;
  113.                 kol_v_stolbce[j]++;
  114.             }
  115.         }
  116.     }
  117.     i_tek = sv_i;
  118.     j_tek = sv_j;
  119.     znaki[i_tek][j_tek] = 1;
  120. }
  121.  
  122. void NewPlan() {
  123. //  bool zapol1[n][m];
  124.     int i_min, j_min, vmax, vmin;
  125.     vmax = 0;
  126.     for (int i = 0; i < n; ++i) {
  127.         for (int j = 0; j < m; ++j) {
  128.             if (delta[i][j] > vmax && !(zapol[i][j])) {
  129.                 vmax = delta[i][j];
  130.                 sv_i = i;
  131.                 sv_j = j;
  132.             }
  133.         }
  134.     }
  135.     if (vmax == 0) return;
  136.     for (int i = 0; i < n; ++i)
  137.         for (int j = 0; j < m; ++j)
  138.             zapol1[i][j] = zapol[i][j];
  139.     Init_cicl();
  140.     do {
  141.         for (int i = 0; i < n; ++i) {
  142.             if (i != i_tek && zapol1[i][j_tek]) {
  143.                 i_tek = i;
  144.                 znaki[i_tek][j_tek] = -1;
  145.                 break;
  146.             }
  147.         }
  148.         if (i_tek == sv_i)  break;
  149.         for (int j = 0; j < m; ++j) {
  150.             if ((j != j_tek) && (zapol1[i_tek][j])) {
  151.                 j_tek = j;
  152.                 znaki[i_tek][j_tek] = 1;
  153.                 break;
  154.             }
  155.         }
  156.         if (kol_v_stolbce[j_tek] < 2) {
  157.             zapol1[i_tek][j_tek] = false;
  158.             Init_cicl();
  159.         }
  160.         if (kol_v_stroke[i_tek] < 2) {
  161.             zapol1[i_tek][j_tek] = false;
  162.             Init_cicl();
  163.         }
  164.     } while (true);
  165.  
  166.     vmin = INT_MAX;
  167.     for (int i = 0; i < n; ++i) {
  168.         for (int j = 0; j < m; ++j) {
  169.             if (znaki[i][j] == -1 && x[i][j] < vmin) {
  170.                 vmin = x[i][j];
  171.                 i_min = i;
  172.                 j_min = j;
  173.             }
  174.         }
  175.     }
  176.  
  177.     zapol[i_min][j_min] = false;
  178.     zapol[sv_i][sv_j] = true;
  179.  
  180.     for (int i = 0; i < n; ++i)
  181.         for (int j = 0; j < m; ++j)
  182.             x[i][j] += znaki[i][j] * vmin;
  183.  
  184.    
  185. }
  186.  
  187. int main(void) {
  188.     a[0] = 270; a[1] = 390; a[2] = 290;
  189.     b[0] = 150; b[1] = 100; b[2] = 250; b[3] = 340; b[4] = 110;
  190.     c[0][0] = 9; c[0][1] = 4; c[0][2] = 6; c[0][3] = 5; c[0][4] = 6;
  191.     c[1][0] = 17; c[1][1] = 11; c[1][2] = 15; c[1][3] = 3; c[1][4] = 7;
  192.     c[2][0] = 20; c[2][1] = 9; c[2][2] = 15; c[2][3] = 7; c[2][4] = 25;
  193.     ser_zap(a, b, x);
  194.     int t;
  195.     Print();
  196.     do {
  197.         Print();
  198.         Potencial();
  199.         Ozenka();
  200.         NewPlan();
  201.         Print();
  202.     } while (!optim());
  203.     Print();
  204.     rez = 0;
  205.     for (int i = 0; i < n; ++i)
  206.         for (int j = 0; j < m; ++j)
  207.             rez += x[i][j] * c[i][j];
  208.     printf("%d\n", rez);
  209.     return 0;
  210. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement