Advertisement
StoneHaos

mod_n9_v18

Jan 27th, 2022
1,116
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <limits.h>
  3. #include <algorithm>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. const int n = 11;
  9. int mtx[n][n] = {
  10.     { 0,  3,  0,  0,  0,  0,  0,  0,  0,  0,  0},
  11.     { 0,  0,  9,  7, 10,  0,  0,  0,  0,  0,  0},
  12.     { 0,  0,  0,  0,  0, 17,  0,  0,  0,  0,  0},
  13.     { 0,  0,  0,  0,  0,  0,  0,  0, 28,  0,  0},
  14.     { 0,  0,  0,  6,  0,  0,  0, 17,  0,  0,  0},
  15.     { 0,  0,  0,  0,  0,  0, 14,  0,  0,  4,  0},
  16.     { 0,  0,  0,  0,  0,  0,  0,  0,  0, 10,  0},
  17.     { 0,  0,  0,  0,  0,  0,  0,  0,  0,  8,  0},
  18.     { 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1},
  19.     { 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1},
  20.     { 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0},
  21. };
  22.  
  23. int tp[n];
  24. int tn[n];
  25. int R[n];
  26.  
  27. int T(int a, int b) {
  28.     return mtx[a][b];
  29. }
  30.  
  31. void TN(int i) {
  32.     int mn = INT_MAX;
  33.     for (int j = 0; j < n; ++ j) {
  34.         if (T(i, j) != 0) {
  35.             if (tn[j] == -1)
  36.                 TN(j);
  37.             mn = min(mn, tn[j] - T(i, j));
  38.         }
  39.     }
  40.     tn[i] = mn;
  41. }
  42.  
  43. int main(void) {
  44.     printf("tp:");
  45.     for (int i = 1; i < n; ++ i) {
  46.         int mx = INT_MIN;
  47.         for (int j = 0; j < n; ++ j) {
  48.             if (T(j, i) != 0)
  49.                 mx = max(mx, tp[j] + T(j, i));
  50.         }
  51.         tp[i] = mx;
  52.         printf(" %d", tp[i]);
  53.     }
  54.     printf("\n");
  55.     for (int i = 0; i < n; ++ i)
  56.         tn[i] = -1;
  57.     tn[n - 1] = tp[n - 1];
  58.     for (int i = n - 2; i >= 0; -- i) {
  59.         TN(i);
  60.     }
  61.     printf("tn:");
  62.     for (int i = 0; i < n; i ++) {
  63.         printf(" %d", tn[i]);
  64.     }
  65.     printf("\n");
  66.  
  67.     printf("R:");
  68.     for (int i = 0; i < n; ++ i) {
  69.         R[i] = tn[i] - tp[i];
  70.         printf(" %d", R[i]);
  71.     }
  72.     printf("\n");
  73.  
  74.     printf("critical way:");
  75.     int x = 0;
  76.     while (x != n - 1) {
  77.         for (int i = x; i < n; ++ i) {
  78.             if (T(x, i) != 0 && R[i] == 0) {
  79.                 printf(" %d", x + 1);
  80.                 x = i;
  81.                 break;
  82.             }
  83.         }
  84.     }
  85.     printf(" %d\n", n);
  86.  
  87.     printf("\n");
  88.     for (int i = 0; i < n; ++ i) {
  89.         for (int j = i; j < n; ++ j) {
  90.             if (T(i, j) != 0) {
  91.                 printf("Rn(%d,%d) = %d\n", i + 1, j + 1, tn[j] - tp[i] - T(i, j));
  92.             }
  93.         }
  94.     }
  95.     printf("\n");
  96.     for (int i = 0; i < n; ++ i) {
  97.         for (int j = i; j < n; ++ j) {
  98.             if (T(i, j) != 0) {
  99.                 printf("Rc(%d,%d) = %d\n", i + 1, j + 1, tp[j] - tp[i] - T(i, j));
  100.             }
  101.         }
  102.     }
  103.     return 0;
  104. }
Advertisement
RAW Paste Data Copied
Advertisement