网络流总结（二）

duoerbasilu

浏览: 1541659 次

最近访客更多访客>>

Beryl

leontius

xld800

HBSU614

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (1527)

社区版块

存档分类

2012-07 ( 651)
2012-06 ( 163)
2012-05 ( 163)
更多存档...

这些天学习网络流，总结了一下用到的主要算法，主要从下面几个方面来介绍

一、常见的几种算法

二、这些算法的复杂度

三、这些算法适合处理的问题

四、算法模板

FF方法（Ford_Fulkerson）：

所有增广路径问题都是以Ford_Fulkerson方法为基础，之所以称为方法而不是算法，因为它提供的是一种思想。

Ford_Fulkerson(s,t)
	f = 0,对自定义流f进行初始化
	while 存在增广路径p 
		do 沿p对流f进行增广 //f += MaxFlow,MaxFlow为增广路径中最大流
	return p; //p即为整个图中最大流

我原来这个方法一直没有得到很好的理解，汗，现在才明白为什么叫增广路径，f是自己定义的一个流，原来图中存在容量c(i,j)，在不超过c(i,j)的情况下尽情对f流进行增光，这样得到的f即为最大流。残留容量cf(i, j) = c(i, j) - f(i, j),网中所有cf(i, j) > 0 的边组成一个残留网络，每次对f进行一次增广，则cf(i, j) -= flow; cf(j, i) += flow;对反向边进行操作也是后面才了解，是为了给后面查找增广路径时候提供更多的选择，如果这个点不通了，则返回到上一个节点继续查找。这样最后残留网络中反向边流量cf(j, i) = f(i, j)。增广路径即s 到 t的一条路径。
沿增广路径进行增广的操作一般都是相同的，主要算法不同体现在对增广路径的寻找过程中。

Sap算法（Shortest Augmenting Path）:

这是一类算法，每次寻找最短最广路径进行增广，后面的DK，Dinic算法都是基于此

Sap()
	ans = 0
	while 寻找增广路径
		do 存在一条最短增广路径p
		flow = min(cf(i, j) [i,j] ∈ E)
		ans += flow
		沿p进行增广 //正反两步
	return ans;

EK算法（Edmonds_Karp）：

BFS寻找最短最广路径，最简单的一种寻找最短最广路径方法，算法复杂度为O(V*E^2)，因为BFS寻找最短路径需要搜索完所有小于最短距离的边才能找到终点，所以算法复杂度比较高。

算法模板：

int path[nMax];
int queue[nMax];
int flow[nMax];
int s, t;
ek_Bfs()//算法复杂度O(E)
{
	int front, rear;
	front = rear = 0;
	queue[rear ++] = s;
	flow[s] = INF;
	while(front < rear)
	{
		int u = queue[front ++];
		if(u == t) break;
		for(int v = 0; v < n; ++ v)//其实就是搜索临边的意思
		{
			if(path[v] == -1 && map[u][v])
			{
				flow[v] = min(flow[u], map[u][v]);
				path[v] = u;
				queue[rear ++] = v;
			}
		}
	}
	if(path[t] == -1) return 0;
	else return flow[t];
}
ek_Flow()//算法复杂度O(V*E)
{
	int MaxFlow = 0;
	while((flow = ek_Bfs())
	{
		MaxFlow += flow;
		int cur = t;
		while(cur != s)
		{
			int pre = path[cur];
			map[pre][cur] -= flow;
			map[cur][pre] += flow;
			cur = pre;
		}
	}
	return MaxFlow;
}

Dinic算法：

算法思路：BFS寻找终点太慢，DFS又无法保证搜索到最短路径，结合这两种算法的优势，利用构造分层网络的算法来寻找最短路径，这个算法又称为阻塞流算法。
首先从s点处进行bfs搜索，dis[s] = 0，然后层次数依次增加，如果搜索到t，则结束。dfs进行搜索，逐层搜索，进行d[v] == d[u] + 1判断，任意一条路径即为最短路径。
Dinic 算法的另一个优化之处：找一条增广路径同时可以找到多条，类似增广路径树。如果cur顶点的总残余流量不为零，这样我们就不必要从起点再次开始寻找增广路，而是从cur顶点出发直接开始，这样就会减少了重复计算，提高效率。

时间复杂度：O(V^2*E)

模板：

struct Edge
{
	int v, w, next;
}adj[mMax];//邻接表，注意这里的下标是mMax，一般为nMax的10倍
int head[nMax];//顶点对应第一条弧
int dis[nMax];//到s的距离
int queue[nMax];
int s, t;//源点、汇点

int dinicBfs()//BFS建层次图，只要发现存在可行弧即可结束
{
	int front, rear;
	front = rear = 0;
	queue[rear ++] = s;
	memset(dis, -1, sizeof(dis));
	dis[s] = 0;
	while(front < rear)
	{
		int u = queue[front ++];
		for(int id = head[u]; id != -1; id = adj[id].next)
		{
			int v = adj[id].v;
			if(adj[id].w && dis[v] == -1)
			{
				dis[v] = dis[u] + 1;
				if(v == t) return 1;
				queue[rear ++] = v;
			}
		}
	}
	return 0;
}

int dinicDfs(int cur, int cost = INF)//DFS寻找增广路经，其中可能涉及到多条增广路经
	//①、②处，曾经漏写
{
	if(cur == t) return cost;//①
	int flow;//从v开始搜索到增广路经的最大流
	int ans = 0;//多条增广路经最大流之和
	for(int id = head[cur]; id != -1; id = adj[id].next)
	{
		int v = adj[id].v;
		if(adj[id].w && dis[v] == dis[cur] + 1 && (flow = dinicDfs(v, min(cost, adj[id].w))))
		{
			adj[id].w -= flow;
			adj[id ^ 1].w += flow;
			cost -= flow;
			ans += flow;
			if(!cost) break;//②，如果剩余流量为0，则需要退出
		}
	}
	return ans;
}

int dinicFlow()
{
	int ans = 0;
	while(dinicBfs())//判断是否存在可行弧
		ans += dinicDfs(s);
	return ans;
}

ISAP算法(sap优化算法)：

算法思路：Dinic算法效率已经很高，然而算法的优化时无尽头的，Dinic算法需要多次计算层次图，增加了复杂度，是不是可以不多次计算层次图呢？答案是肯定的，这就是ISAP算法。
ISAP计算的是反向图的层次图，作用与原图的层次图一样。计算反向图的层次图是便于重新给顶点标号，即计算层次图，具体做法：在查找<u,v>的时候，MinDis = min(dis[v])，这样查找玩所有与顶点u相关的边之后，dis[u] = dis[v] + 1，从而得到新的层次图。在刚开始寻找的时候，我们也不需要计算层次图，对所有dis[]都赋值为0即可，对效率没有多大影响。
另外ISAP算法的另一个优化在于：如果层次图出现断层，则直接结束。

时间复杂度：O(V^2*E)

模板：

struct Edge
{
	int v, w, next;
}adj[mMax];
int head[nMax];
int dis[nMax];
int vn[nMax];//每一层顶点的个数，便于判断层次图中是否出现断层
int s, t;
int NV;//图中总顶点数

int sapDfs(int cur, int cost)
{
	if(cur == t) return cost;
	int flow;
	int ans = 0;
	int MinDis = NV;
	for(int id = head[cur]; id != -1; id = adj[id].next)
	{
		int v = adj[id].v;
		if(adj[id].w)//下面两个if不能合并，因为需要对MinDis进行赋值
		{
			if(dis[v] + 1 == dis[cur])
			{
				flow = sapDfs(v, min(cost, adj[id].w));//这个不应该写到上面if语句中，因为需要下面的if语句进行断层的判断。
				adj[i].w -= flow;
				adj[i ^ 1].w += flow;
				ans += flow;
				cost -= flow;
				if(dis[s] >= NV) return ans;//判断从v进行dfs搜索的过程中是否出现断层
				if(!cost) break;//如果剩余流量为0，则需要跳出循环
			}
			if(dis[v] < MinDis)
				MinDis = dis[v];//MinDis存储与cur相连顶点的最小层次数
		}
	}
	if(!ans)
	{
		if(-- vn[dis[cur]] == 0) dis[s] = NV;//判断是否出现断层
		dis[cur] = MinDis + 1;//对顶点进行重标记
		++ vn[dis[cur]];
	}
	return ans;
}

int sapFlow()
{
	memset(dis, 0, sizeof(dis));
	memset(vn, 0, sizeof(vn));
	vn[0] = NV;
	int ans = 0;
	while(dis[s] < NV)//dis[s] < NV其实是你自己定义的一个终止条件，你也可以使用flag标记，因为如果真的出现dis[s] < NV，则其中必然会出现断层
		ans += sapDfs(s);
	return ans;
}

匈牙利算法：

匈牙利算法，主要处理二分图最大匹配问题，算法复杂度为O(V^3)

算法模板：

int link[nMax];
int useif[nMax];
int n, m;//A、B集合分别对应的顶点数

int getPath(int x)//寻找匹配边，算法复杂度O(m^2)，即O(V^2)
{
	for(int i = 0; i < m; ++ i)
	{
		if(!useif[i] && map[x][i])
		{
			useif[i] = 1;
			if(link[i] == -1 && getPath(link[i]))//如果点i被匹配，检查点link[i]是否存在另外可匹配边
			{
				link[i] = x;
				return 1;
			}
		}
	}
	return 0;
}

int getNum()//返回最大匹配数，算法复杂度O(n)，即O(V)
{
	int num = 0;
	memset(link, -1, sizeof(link));
	for(int i = 0; i < n; ++ i)
	{
		memset(useif, 0, sizeof(useif));
		num += getPath(i);
	}
	return num;
}

以上内容只是我的理解，这两篇博文总结的很不错，推荐一下！

http://www.cnblogs.com/longdouhzt/archive/2012/05/20/2510753.html

http://www.cnblogs.com/longdouhzt/archive/2012/05/20/2510743.html

图论继续学习：

http://starfall512.com/?p=272#comment-152

分享到：