Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### hissain.khan's blog

By hissain.khan, history, 8 months ago, ,

I have written a naive max flow with DFS, could anyone review my below code. What to do to improve the code and what are the worst cases where this wont work fine.

#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){ 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);
}


•
• -25
•