网络源总结（二）

网络流总结（二）

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

一、常见的几种算法

二、这些算法的复杂度

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

四、算法模板

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

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