`
kenby
  • 浏览: 724740 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

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;
}
分享到:
评论

相关推荐

    POJ3308-Paratroopers 【Dinic算法求最大流】

    【二分图顶点覆盖-&gt;最小割-&gt;最大流-&gt;Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----&gt; 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573

    Dinic多路增广pascal源码

    Dinic多路增广pascal源码 poj 1273格式

    最大流题解1

    常见的最大流算法有Ford-Fulkerson方法(包括Dinic算法和Edmonds-Karp算法)、Shortest Augmenting Path(SAP)算法等。这些算法的核心思想是寻找增广路径,即从源点到汇点的路径,其容量未达到最大值,通过反复增加...

    POJ2195-Going Home【费用流】

    4. **Dinic算法**:一种解决最大流问题的高效算法,适用于处理有负权边的情况,可以与费用流问题结合。 5. **增广路径**:在费用流问题中,增广路径是指从源点到汇点的路径,沿路径可以增加流量而不会违反任何边的...

    acm新手刷题攻略之poj

    - 最大流问题通常涉及到Ford-Fulkerson算法或者Dinic算法的应用。 4. **网络流** - 推荐题目:[poj3041](https://vjudge.net/problem/POJ-3041)、[poj3020](https://vjudge.net/problem/POJ-3020) - 网络流问题...

    POJ题目分类 POJ题目分类

    2. **图论与网络流**:这一类题目涉及图的遍历(如深度优先搜索、广度优先搜索)、最短路径算法(如Dijkstra、Floyd-Warshall)以及网络流问题(如Ford-Fulkerson方法、 Dinic算法)。 3. **动态规划**:动态规划是...

    上下界网络流

    然后,求出这个图的最大流,如果最大流等于∑downi,那么就是可行流,否则没有可行流。 有源汇的上下界网络流: 在有源汇的上下界网络流中,可以通过添加一条 t-&gt;s 的边,流量限制为[0, inf],将其转换为无源汇...

    网络流_final1

    在求解最大流问题时,可以采用Dinic算法或Shortest Augmenting Path (SAP)算法。 3. **最大权闭合子图**: 最大权闭合子图问题是寻找一个有向图的子图,其中每条边都有权重,且这个子图中任意两点间都有路径,目标...

    剪绳子leetcode-Online-Judge-Solutions:日常在线判断解决方案

    剪绳子leetcode 在线裁判解决方案 每日在线裁判解决方案(主要是LeetCode和Openjudge) 规格 文件格式: [SITE][ID].cpp等 网站简称: OP : LC : LCOF ...POJ ...最大流量 ...最大流量 Dinic算法,建模 1

    kuangbin acm模板超级好用

    2.3 扩展欧几里得算法(求 ax+by=gcd 的解以及逆元) . . . . . . . . . . . . . . . 27 2.4 求逆元 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4.1 扩展欧几里德法 ...

Global site tag (gtag.js) - Google Analytics