hissain.khan's blog

By hissain.khan, history, 6 years 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);
}

Full text and comments »

  • Vote: I like it
  • -25
  • Vote: I do not like it

By hissain.khan, history, 6 years ago, In English

Here I have implemented Quad tree for ranged sum query. Is it possible to improve update with lazy propegation or something like that.

#include <stdio.h>
#define SZ 10

int TT[4 * SZ * SZ];

int AA[4][4] = {
	{ 1, 1, 1, 1 },
	{ 1, 1, 1, 1 },
	{ 1, 1, 1, 1 },
	{ 1, 1, 1, 1 }
};

int bld(int n, int i1, int j1, int i2, int j2){

	if (i1 > i2 || j1 > j2)
		return 0;

	if (i1 == i2 && j1 == j2)
		return TT[n] = AA[i1][i2];

	int mi = i1 + (i2 - i1) / 2;
	int mj = j1 + (j2 - j1) / 2;

	TT[n] = 0;

	TT[n] += bld(4 * n + 1, i1, j1, mi, mj);		// upper left quad
	TT[n] += bld(4 * n + 2, mi + 1, j1, i2, mj);		// lower left quad
	TT[n] += bld(4 * n + 3, i1, mj + 1, mi, j2);		// upper right quad
	TT[n] += bld(4 * n + 4, mi + 1, mj + 1, i2, j2);	// lower right quad

	return TT[n];
}

int qry(int n, int i1, int j1, int i2, int j2, int r1, int c1, int r2, int c2){

	if (i1 > r2 || j1 > c2 || i2 < r1 || j2 < c1 || i1 > i2 || j1 > j2)
		return 0;

	if (i1 >= r1 && j1 >= c1 && i2 <= r2 && j2 <= c2)
		return TT[n];

	int mx = 0;

	int mi = i1 + (i2 - i1) / 2;
	int mj = j1 + (j2 - j1) / 2;

	mx += qry(4 * n + 1, i1, j1, mi, mj, r1, c1, r2, c2);
	mx += qry(4 * n + 2, mi + 1, j1, i2, mj, r1, c1, r2, c2);
	mx += qry(4 * n + 3, i1, mj + 1, mi, j2, r1, c1, r2, c2);
	mx += qry(4 * n + 4, mi + 1, mj + 1, i2, j2, r1, c1, r2, c2);

	return mx;
}


int upd(int n, int i1, int j1, int i2, int j2, int r1, int c1, int r2, int c2, int v){

	if (i1 > r2 || j1 > c2 || i2 < r1 || j2 < c1 || i1 > i2 || j1 > j2)
		return 0;

	if (i1 == i2 && j1 == j2)
		return TT[n] = v;

	Point mx(-1, -1, 0);

	int mi = i1 + (i2 - i1) / 2;
	int mj = j1 + (j2 - j1) / 2;

	mx += upd(4 * n + 1, i1, j1, mi, mj, r1, c1, r2, c2, v);
	mx += upd(4 * n + 2, mi + 1, j1, i2, mj, r1, c1, r2, c2, v);
	mx += upd(4 * n + 3, i1, mj + 1, mi, j2, r1, c1, r2, c2, v);
	mx += upd(4 * n + 4, mi + 1, mj + 1, i2, j2, r1, c1, r2, c2, v);

	return TT[n] = mx;
}

int main(){

	int R, C;

	int x1, y1, x2, y2;

	// Data array Row,Col (RxC)

	R = 4;
	C = 4;

	// Query range (x1, y1) ~ (x2, y2)

	x1 = 0, y1 = 0;
	x2 = 2, y2 = 2;

	int p;

	bld(0, 0, 0, R - 1, C - 1);

	p = qry(0, 0, 0, R - 1, C - 1, x1, y1, x2, y2);

	p = upd(0, 0, 0, R - 1, C - 1, x1, y1, x2, y2, 2); // value = 2

	p = qry(0, 0, 0, R - 1, C - 1, x1, y1, x2, y2);

	return 0;
}

Full text and comments »

  • Vote: I like it
  • -24
  • Vote: I do not like it