第一次写最大流的题,,,用的是最复杂的找增光路的方法,,E-K算法,,用bfs找增广路,网络流刚接触路还很长啊,,,加油,,,
网络流作为一门高级图论,在近几年的信息学竞赛中越来越频繁的出现,而且难度颇深。网络流算法由3大系组成,分别为增广路系,预留推进系,最小割系。下面介绍一下增广路系的网络流算法。
1.ek算法
网络流中基础算法,算法思想是每次用bfs找增广路。
2.dinic算法
理论时间复杂度为O(n^2m),算法思想是先用一个bfs建立层次图,然后用一个dfs(单路增广)不断找增广路。每次增广路用一个栈保存。增广后栈顶元素设为增光路中从s出发可以到达的最远结点。当dfs退出时,重新bfs,重复以上步骤。直到完全不能增广。
3.sap算法
有着与dinic相同的理论复杂度,算法思想与dinic大致相同。也是用dfs不断找增广路。只是找不到的时候进行重标号。重标号的过程是这样的:在当前节点相邻的节点中选择标号最小的加1,并设为当前弧。当s的标号=n时,退出增广过程,并找到了最大流。
附:我的网络流速度测试说明:dinic加了优化之后3000点比sap要快,>3000点则比sap要慢。
我的算法优化:
dinic:gap+弹栈+当前弧
sap:gap+当前弧
分享到:
相关推荐
北大POJ3414-Pots 解题报告+AC代码
poj3045的源码,很久以前写的,语言是C++
poj 2820 古代密码 http://poj.grids.cn/problem?id=2820 可直接运行
poj2880 输入一个英文句子,长度不超过40个字符。编写程序,输出句子中最长的一个单词。 http://poj.grids.cn/problem?id=2880 可直接运行
http://poj.grids.cn/problem?id=2774 POJ 2774 木棒加工 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要得到的小段的数目是给定了。当然,我们希望得到的小段越长越好,你的任务是计算能够...
经典的0-1背包问题. 适合新手学习. 原题网址:http://poj.grids.cn/problem?id=2773
poj1691解题报告 题目来源:http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1691(POJ No.1691) 解法: 搜索
//http://poj.org/problem?id=1611 #include using namespace std; const int maxn = 30010; int f[maxn],num[maxn],n,m; int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); } int main() { while(cin...
如输入数据为 3 11011000 输出为 IIIBIFFIBFBBBFF 第4题(http://poj.org/problem?id=1050) To the Max Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 25250 Accepted: 13051 Description Given a ...
POJ problems ID Problem C++ 1001 1002 1003 1004 1006 1007 专题分类 (一)简单搜索 ID Problem C++ Source 1 HDU 2553 (精简版) 2 HDU 1312 3 POJ 3984 4 POJ 2251 5 POJ 3278 6 POJ 3279 7 ZOJ 1002 8 POJ 1321 9...
POJ problems ID Problem C++ 1001 1002 1003 1004 1006 1007 专题分类 (一)简单搜索 ID Problem C++ Source 1 HDU 2553 (精简版) 2 HDU 1312 3 POJ 3984 4 POJ 2251 5 POJ 3278 6 POJ 3279 7 ZOJ 1002 8 POJ 1321 9...