hissain.khan's blog

By hissain.khan, history, 4 days ago, In English,

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);
}
 
 
 
 
  • Vote: I like it  
  • -25
  • Vote: I do not like it