2
\$\begingroup\$

I have written a naive max flow with DFS, could anyone review my below code. What can be done to improve the code and what are the worst cases where this won’t work acceptably?

#include <stdio.h>
#include <stdlib.h>

#define SZ 20

int flow[SZ][SZ];
int residue[SZ][SZ];
int N, E, u, v, c;
int Source, Sink;

int visited[SZ];

inline int min(int a, int b){ return a < b ? a : b; }
inline int abs(int n){ return n < 0 ? -n : n; }

void print(int graph[SZ][SZ]){

    for (register int i = 0; i < N; i++){
        for (register int j = 0; j < N; j++){
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

int dfs(int u, int rescap){

    if (u == Sink || rescap == 0){ return rescap;}

    visited[u] = 1;

    for (register int v = 0; v < N; v++){

        if (visited[v] == 0 && residue[u][v]){

            int r = dfs(v, min(residue[u][v], rescap));

            if (r) {

                flow[u][v] += r;
                residue[u][v] -= r;
                residue[v][u] += r;

                if (flow[u][v] > flow[v][u]){
                    flow[u][v] -= flow[v][u];
                    flow[v][u] = 0;
                }
                else {
                    flow[v][u] -= flow[u][v];
                    flow[u][v] = 0;
                }

                visited[u] = 0;
                return r;
            }
        }
    }

    visited[u] = 0;

    return 0;
}

/*void input(){

    freopen("input.txt", "wt", stdout);

    printf("%d %d\n", SZ, 5*SZ);

    for (register int i = 0; i < 5 * SZ; i++){

        int a = rand() % SZ;
        int b = rand() % SZ;
        int c = rand() % SZ;

        printf("%d %d %d\n", a, b, c);
    }

    fclose(stdout);
}*/

void maxflow(){

    freopen("input.txt", "rt", stdin);
    scanf("%d %d", &N, &E);

    Source = 0;
    Sink = N - 1;

    for (register int i = 0; i < E; i++){
        scanf("%d %d %d", &u, &v, &c);
        residue[u][v] = c;
    }

    int total = 0;
    int rescap = 0;
    while (rescap = dfs(Source, 1 << 30))
        total += rescap;

    printf("total flow: %d\n", total);

    print(flow);
    print(residue);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.