10

#include <stdio.h>
#include <limits.h>

int max(int a, int b) {
    return ((a > b) ? a : b);
}
int min(int a, int b) {
    return ((a < b) ? a : b);
}

const int n = 11;
int mtx[n][n] = {
    { 0,  5,  0,  0,  0,  0,  0,  0,  0,  0,  0},
    { 0,  0,  7,  7,  7,  0,  0,  0,  0,  0,  0},
    { 0,  0,  0,  0,  0, 13,  0,  0,  0,  0,  0},
    { 0,  0,  0,  0,  0,  0,  0,  0, 14,  0,  0},
    { 0,  0,  0,  5,  0,  0,  0, 11,  0,  0,  0},
    { 0,  0,  0,  0,  0,  0, 18,  0,  0,  4,  0},
    { 0,  0,  0,  0,  0,  0,  0,  0, 10,  7,  0},
    { 0,  0,  0,  0,  0,  0,  0,  0,  0, 11,  0},
    { 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1},
    { 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1},
    { 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0},
};

/*const int n = 5;
int mtx[n][n] = {
    {0, 2, 4, 0, 0},
    {0, 0, 3, 9, 0},
    {0, 0, 0, 5, 0},
    {0, 0, 0, 0, 6},
    {0, 0, 0, 0, 0},
};*/

int tp[n];
int tn[n];
int R[n];
int cw[n];

int T(int a, int b) {
    return mtx[a][b];
}
//Подсчёт tp
void ctp(int i) {
    int mx = INT_MIN;
    for (int j = 0; j < n; ++ j) {
        if (T(j, i) != 0)
            mx = max(mx, tp[j] + T(j, i));
    }
    tp[i] = mx;
}
//Подсчёт tn
void ctn(int i) {
    int mn = INT_MAX;
    for (int j = 0; j < n; ++ j) {
        if (T(i, j) != 0) {
            if (tn[j] == -1)
                ctn(j);
            mn = min(mn, tn[j] - T(i, j));
        }
    }
    tn[i] = mn;
}
//Вывод Rn
void outrn() {
    for (int i = 0; i < n; ++ i) {
        for (int j = i; j < n; ++ j) {
            if (T(i, j) != 0) {
                printf("Rn(%d,%d) = %d\n", i + 1, j + 1, tn[j] - tp[i] - T(i, j));
            }
        }
    }
}
//Вывод Rc
void outrc() {
    for (int i = 0; i < n; ++ i) {
        for (int j = i; j < n; ++ j) {
            if (T(i, j) != 0) {
                printf("Rc(%d,%d) = %d\n", i + 1, j + 1, tp[j] - tp[i] - T(i, j));
            }
        }
    }
}
//Вычисление критического пути
int ccw(int i) {
    if (i == n - 1) {
        cw[0] = i;
        return 1;
    }
    for (int j = i; j < n; ++ j) {
        if (T(i, j) != 0 && R[j] == 0) {
            int r = ccw(j);
            cw[r] = i;
            return r + 1;
        }
    }
}

int main(void) {
    //tp
    for (int i = 1; i < n; ++ i) {
        ctp(i);
    }

    //tn
    for (int i = 0; i < n; ++ i)
        tn[i] = -1;
    tn[n - 1] = tp[n - 1];
    for (int i = n - 2; i >= 0; -- i) {
        ctn(i);
    }

    //R
    for (int i = 0; i < n; ++ i)
        R[i] = tn[i] - tp[i];


    printf("tp:");
    for (int i = 0; i < n; ++ i)
        printf(" %d", tp[i]);
    printf("\n");

    printf("tn:");
    for (int i = 0; i < n; ++ i)
        printf(" %d", tn[i]);
    printf("\n");

    printf("R:");
    for (int i = 0; i < n; ++ i)
        printf(" %d", R[i]);
    printf("\n");

    printf("critical way:");
    int brd = ccw(0);
    for (int i = brd - 1; i >= 0; -- i) {
        printf(" %d", cw[i] + 1);
    }
    printf("\n");

    printf("\n");
    outrn();
    printf("\n");
    outrc();
    return 0;
}