poj 1273 dinic算法求最大流

 

#include <stdio.h>
#include <string.h>

//#define DEBUG

#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__) 
#else
#define debug(...)
#endif

#define N 201
#define MAXQSIZE 1000
#define MAX_INT 2000000

#define min(a, b) (a) < (b) ? (a) : (b)

int		graph[N][N];
int		n;

int 	queue[MAXQSIZE];
int		front, rear;

int		level[N];
int		parent[N];	/* bfs过程中保存增广路径的路线 */
int		augment[N];	/* augment[u表示]从源点到定点u的最小流量 */

void push(int e) 
{
	if ((rear+1) % MAXQSIZE == front) {
		printf("queue is full...\n");
		exit(0);
	}
	queue[rear] = e;
	rear = (rear+1) % MAXQSIZE;
}

int pop()
{
	int		e;

	e = queue[front];
	front = (front+1) % MAXQSIZE;
	return e;
}

void init_queue()
{
	front = rear = 0;
}

int  bfs(int s, int e) 
{
	int		u, v;

	init_queue();
	memset(level, -1, sizeof(level));

	push(s);
	level[s] = 0;
	while (front != rear) {
		u = pop();
		if (u == e) {
			for (v = s; v <= e; v++) {
				debug("level[%d] = %d\n", v, level[v]);
			}
			return 1;
		}
		for (v = 0; v <= e; v++) {
			if (level[v] == -1 && graph[u][v] > 0) {
				push(v);
				level[v] = level[u] + 1;
			}
		}
	}
	return 0;
}

int dinic(int s, int e)
{
	int		u, v, max_flow, aug, w, degree;

	max_flow = 0;
	augment[s] = MAX_INT;
	while (bfs(s, e)) {
		u = s;
		parent[s] = -1;
		while (u != -1) {	/* 如果u回溯到-1, 结束 */
			if (u == e) {	/* 找到一条增广路径 */
				max_flow += augment[e];
				aug = augment[e];
				debug("找到一条增广路径, augment = %d\n", aug);
				for (v = e, w = parent[e]; v > s; v = w, w = parent[w]) {
					debug("%d<--", v);
					graph[w][v] -= aug;
					graph[v][w] += aug;
					augment[v] -= aug;
					if (graph[w][v] == 0) u = w; 
				}
				debug("%d\n", v);
			}
			/* 从顶点u往下找邻接点 */
			degree = 0;
			for (v = s; v <= e; v++) {
				if (graph[u][v] > 0 && (level[u]+1) == level[v]) {
					augment[v] = min(augment[u], graph[u][v]);
					parent[v] = u;
					degree++;
					u = v;
					break;
				}
			}
			if (degree == 0) {	/* 没有邻接点, 回溯到上一个点 */
				debug("顶点%d走不通\n", u);
				level[u] = MAX_INT;
				u = parent[u];
			}
		}
	}
	return max_flow;
}

int main()
{
	int		m, u, v, w;

	while (scanf("%d", &m) != EOF) {
		memset(graph, 0, sizeof(graph));
		scanf("%d", &n);
		while (m--) {
			scanf("%d %d %d", &u, &v, &w);
			graph[u-1][v-1] += w;
		}
		printf("%d\n", dinic(0, n-1));
	}
	return 0;
}