StoneHaos

10

Jan 25th, 2022 (edited)
713
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <limits.h>
  3.  
  4. int max(int a, int b) {
  5.     return ((a > b) ? a : b);
  6. }
  7. int min(int a, int b) {
  8.     return ((a < b) ? a : b);
  9. }
  10.  
  11. const int n = 11;
  12. int mtx[n][n] = {
  13.     { 0, 12,  0,  0,  0,  0,  0,  0,  0,  0,  0},
  14.     { 0,  0,  7,  8,  6,  0,  0,  0,  0,  0,  0},
  15.     { 0,  0,  0,  0,  0, 17,  0,  0,  0,  0,  0},
  16.     { 0,  0,  0,  0,  0,  0,  0,  0, 12,  0,  0},
  17.     { 0,  0,  0,  6,  0,  0,  0, 17,  0,  0,  0},
  18.     { 0,  0,  0,  0,  0,  0, 13,  0,  0,  6,  0},
  19.     { 0,  0,  0,  0,  0,  0,  0,  0, 13,  6,  0},
  20.     { 0,  0,  0,  0,  0,  0,  0,  0,  0, 16,  0},
  21.     { 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1},
  22.     { 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1},
  23.     { 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0},
  24. };
  25.  
  26. /*const int n = 5;
  27. int mtx[n][n] = {
  28.     {0, 2, 4, 0, 0},
  29.     {0, 0, 3, 9, 0},
  30.     {0, 0, 0, 5, 0},
  31.     {0, 0, 0, 0, 6},
  32.     {0, 0, 0, 0, 0},
  33. };*/
  34.  
  35. int tp[n];
  36. int tn[n];
  37. int R[n];
  38. int cw[n];
  39.  
  40. int T(int a, int b) {
  41.     return mtx[a][b];
  42. }
  43. //Подсчёт tp
  44. void ctp(int i) {
  45.     int mx = INT_MIN;
  46.     for (int j = 0; j < n; ++ j) {
  47.         if (T(j, i) != 0)
  48.             mx = max(mx, tp[j] + T(j, i));
  49.     }
  50.     tp[i] = mx;
  51. }
  52. //Подсчёт tn
  53. void ctn(int i) {
  54.     int mn = INT_MAX;
  55.     for (int j = 0; j < n; ++ j) {
  56.         if (T(i, j) != 0) {
  57.             if (tn[j] == -1)
  58.                 ctn(j);
  59.             mn = min(mn, tn[j] - T(i, j));
  60.         }
  61.     }
  62.     tn[i] = mn;
  63. }
  64. //Вывод Rn
  65. void outrn() {
  66.     for (int i = 0; i < n; ++ i) {
  67.         for (int j = i; j < n; ++ j) {
  68.             if (T(i, j) != 0) {
  69.                 printf("Rn(%d,%d) = %d\n", i + 1, j + 1, tn[j] - tp[i] - T(i, j));
  70.             }
  71.         }
  72.     }
  73. }
  74. //Вывод Rc
  75. void outrc() {
  76.     for (int i = 0; i < n; ++ i) {
  77.         for (int j = i; j < n; ++ j) {
  78.             if (T(i, j) != 0) {
  79.                 printf("Rc(%d,%d) = %d\n", i + 1, j + 1, tp[j] - tp[i] - T(i, j));
  80.             }
  81.         }
  82.     }
  83. }
  84. //Вычисление критического пути
  85. int ccw(int i) {
  86.     if (i == n - 1) {
  87.         cw[0] = i;
  88.         return 1;
  89.     }
  90.     for (int j = i; j < n; ++ j) {
  91.         if (T(i, j) != 0 && R[j] == 0) {
  92.             int r = ccw(j);
  93.             cw[r] = i;
  94.             return r + 1;
  95.         }
  96.     }
  97. }
  98.  
  99. int main(void) {
  100.     //tp
  101.     for (int i = 1; i < n; ++ i) {
  102.         ctp(i);
  103.     }
  104.  
  105.     //tn
  106.     for (int i = 0; i < n; ++ i)
  107.         tn[i] = -1;
  108.     tn[n - 1] = tp[n - 1];
  109.     for (int i = n - 2; i >= 0; -- i) {
  110.         ctn(i);
  111.     }
  112.  
  113.     //R
  114.     for (int i = 0; i < n; ++ i)
  115.         R[i] = tn[i] - tp[i];
  116.  
  117.  
  118.     printf("tp:");
  119.     for (int i = 0; i < n; ++ i)
  120.         printf(" %d", tp[i]);
  121.     printf("\n");
  122.  
  123.     printf("tn:");
  124.     for (int i = 0; i < n; ++ i)
  125.         printf(" %d", tn[i]);
  126.     printf("\n");
  127.  
  128.     printf("R:");
  129.     for (int i = 0; i < n; ++ i)
  130.         printf(" %d", R[i]);
  131.     printf("\n");
  132.  
  133.     printf("critical way:");
  134.     int brd = ccw(0);
  135.     for (int i = brd - 1; i >= 0; -- i) {
  136.         printf(" %d", cw[i] + 1);
  137.     }
  138.     printf("\n");
  139.  
  140.     printf("\n");
  141.     outrn();
  142.     printf("\n");
  143.     outrc();
  144.     return 0;
  145. }
RAW Paste Data Copied