墙裂推荐这篇博客主要写的算法都正确,而且都有一些可取之处。
01:Edmonds-Karp 算法
EK 算法据说是最简单的。
但大家都是这么评价 EK 算法的:由于 EK 算法容易超时,所以这个在比赛中不怎么用。
可是我对最大流太懵逼了,还是从最简单、最辣鸡的开始吧!
稀里糊涂地模了一个板子,感觉就差不多了。
参考博客链接,理解不动就只能先放弃呗!
简单讲一下现在的理解:
- bfs 查找有无从源点 s 到汇点 t 的路,bfs 的过程中记录路径在 pre 数组中。
bfs 采用队列方式,需要另开一个 vis 数组避免重复遍历,然后只要到大汇点 t 就结束 bfs 返回 true,若 bfs 跑完仍然没有找到汇点 t 就返回 false,无路可走说明已经得到最大流。
2.bfs 失败说明已经找到最大流,结束循环。
若 bfs 返回 true,就遍历两次得到的路径。
第一次找到路径上的最小流,为该路径上的最大流,加入到结果中。
第二次将用过的边(u,v)减去本次的最大流,并建立反向边(v,u)大小为本次最大流。
while 循环结束时 return 结果 flow 就 OK。
思路简单,但理解的不是很彻底,勉强吧!
EK 算法板子/poj1273 Drainage Ditches(排水沟 AC 代码)
这道题目非常的水,这应该是我第一次在 poj 上看到自己的代码运行时间为 0ms
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define MAXN 205
#define INF 0x3f3f3f3f
using namespace std;
int net[MAXN][MAXN];//remain network, initialized as original graph
int pre[MAXN];
int N, M;
bool bfs(int s, int t)//find an augmented path from s to t
{
int now;
queue<int> que;
memset(pre, -1, sizeof(pre));
pre[s] = s;
que.push(s);
while(!que.empty())
{
now = que.front(); que.pop();
for(int i = 1; i < N+1; i++)
{
if(net[now][i] && pre[i] == -1)
{
pre[i] = now;
if(i == t)
return true;
que.push(i);
}//end if
}//end for
}//end while
return false;
}
int EdmondsKarp(int s, int t)
{
#define v pre[u]
int flow = 0;
while(bfs(s, t))
{
int d = INF;
for(int u = t; u != s; u = v)
{
d = min(d, net[v][u]);
}
for(int u = t; u != s; u = v)
{
net[v][u] -= d;
net[u][v] += d;
}
flow += d;
}
return flow;
#undef v
}
int main()
{
while(~scanf("%d%d", &M, &N))
{
int a, b, d;
memset(net, 0, sizeof(net));
for(int i = 1; i < M+1; i++)
{
scanf("%d%d%d", &a, &b, &d);
net[a][b] += d;//pay attention to repetitive edges
}
printf("%d\n", EdmondsKarp(1, N));
}
return 0;
}
02:Dinic 算法
Dinic 算法在 EK 算法的基础上增加了分层图的概念。
就是计算一下每个点到源点 s 的 dis(就是边权值为 1 时的距离呗)
在普通情况下, DINIC 算法时间复杂度为 O(V^2E)
在二分图中, DINIC 算法时间复杂度为 O(\sqrt VE)
这个现在还不懂。
HDU 3549 Flow ProblemDinicAC 代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define MAXN 100100
#define INF 0x3f3f3f3f
using namespace std;
struct edge{//chain forward star
int to;
int next;
int val;
};
edge Edge[MAXN];
int head[MAXN];
int cnt;
void add_edge(int u, int v, int w)
{
Edge[cnt].to = v;
Edge[cnt].next = head[u];
Edge[cnt].val = w;
head[u] = cnt++;
}
int dis[MAXN];
bool bfs(int s, int t)//mark the no-weight distance to s (run once, move just 1)
{
queue<int> que;
memset(dis, -1, sizeof(dis));
que.push(s); dis[s] = 0;
while(!que.empty())
{
int now = que.front(); que.pop();
for(int i = head[now]; i != -1; i = Edge[i].next)//Traverse all edges starting from now
{
int v = Edge[i].to;
if(Edge[i].val && dis[v] == -1)
{
dis[v] = dis[now] + 1;
if(v == t)
return true;
que.push(v);
}
}
}
return false;
}
int N, M;
int dfs(int now, int left)//left: eesidual/剩余 flow
{
if(now == N)
return left;
int used = 0;
for(int i = head[now]; i != -1; i = Edge[i].next)//Traverse all edges starting from s
{
int v = Edge[i].to;
if(Edge[i].val && dis[v] == dis[now] + 1)
{
int d = dfs(v, min(left-used, Edge[i].val));
Edge[i].val -= d;
Edge[i^1].val += d;
used += d;
if(used == left)
return used;
}
}
return used;
}
int Dinic(int s, int t)
{
int max_flow = 0;
while(bfs(s, t))
max_flow += dfs(s, INF);
return max_flow;
}
int main()
{
int Case;
scanf("%d", &Case);
int ct = 1;
while (Case--)
{
memset(head, -1, sizeof(head));
cnt = 0;
scanf("%d%d", &N, &M);
int a, b, d;
for (int i = 1; i < M+1; i++)
{
scanf("%d%d%d", &a, &b, &d);
add_edge(a, b, d);
add_edge(b, a, 0);//construct the reverse edge
}
printf("Case %d: %d\n", ct, Dinic(1, N));
ct++;
}
return 0;
}
用 EK 算法也写了一份也 AC 了.
感觉现在看的例题都太入门了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define MAXN 1010
#define INF 0x3f3f3f3f
using namespace std;
int net[MAXN][MAXN];//remain network, initialized as original graph
int pre[MAXN];
int N, M;
bool bfs(int s, int t)//find an augmented path from s to t
{
int now;
queue<int> que;
memset(pre, -1, sizeof(pre));
pre[s] = s;
que.push(s);
while(!que.empty())
{
now = que.front(); que.pop();
for(int i = 1; i < N+1; i++)
{
if(net[now][i] && pre[i] == -1)
{
pre[i] = now;
if(i == t)
return true;
que.push(i);
}//end if
}//end for
}//end while
return false;
}
int EdmondsKarp(int s, int t)
{
#define v pre[u]
int flow = 0;
while(bfs(s, t))
{
int d = INF;
for(int u = t; u != s; u = v)
{
d = min(d, net[v][u]);
}
for(int u = t; u != s; u = v)
{
net[v][u] -= d;
net[u][v] += d;
}
flow += d;
}
return flow;
#undef v
}
int main()
{
int Case;
scanf("%d", &Case);
int ct = 1;
while (Case--)
{
memset(net, 0, sizeof(net));
scanf("%d%d", &N, &M);
int a, b, d;
for (int i = 1; i < M+1; i++)
{
scanf("%d%d%d", &a, &b, &d);
net[a][b] += d;//construct the reverse edge
}
printf("Case %d: %d\n", ct, EdmondsKarp(1, N));
ct++;
}
return 0;
}
优化
多路增广
每次不是寻找一条增广路,而是在 DFS 中,只要可以就递归增广下去,实际上形成了一张增广网。
当前弧优化
对于每一个点,都记录上一次检查到哪一条边。因为我们每次增广一定是彻底增广(即这条已经被增广过的边已经发挥出了它全部的潜力,不可能再被增广了),下一次就不必再检查它,而直接看第一个未被检查的边。
优化之后渐进时间复杂度没有改变,但是实际上能快不少。
实际写代码的时候要注意,head 数组初始值为-1,存储时从 0 开始存储,这样在后面写反向弧的时候比较方便,直接异或即可。
关于复制 head 的数组 cur;目的是为了当前弧优化。已经增广的边就不需要再走了.
但是有自环的时候或者因为一些其他原因,cur 数组可能会导致 TLE,不信你试一下 HDU 3549 Flow Problem
上面纯属屁话,优化不会导致 TLE,但我还不知道那段代码为什么 TLE(可能时是数组不够大,但
数组不够大怎么就 TLE 了呢,理解不懂就别理解了)。改了一下 dfs 的思想,成功就返回,下次再继续跑就行了,另外 auto 用在取 que.front()时可以加速几十秒,很好用,感觉很帅!
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define MAXN 2010
#define INF 1e9+7
using namespace std;
struct edge{//chain forward star
int to;
int next;
int val;
};
edge Edge[MAXN];
int head[MAXN];
int cur[MAXN];
int cnt;
void add_edge(int u, int v, int w)
{
Edge[++cnt].to = v;
Edge[cnt].next = head[u];
Edge[cnt].val = w;
head[u] = cnt;
}
int N, M;
int dis[MAXN];
bool bfs(int s, int t)//mark the no-weight distance to s (run once, move just 1)
{
int i;
queue<int> que;
memset(dis, 0, sizeof(dis));
que.push(s); dis[s] = 1;
while(!que.empty())
{
auto now = que.front(); que.pop();//The auto here can speed up your code!!!!
for(i = head[now]; i; i = Edge[i].next)//Traverse all edges starting from now
{
int v = Edge[i].to, c = Edge[i].val;
if(c && !dis[v])
{
dis[v] = dis[now] + 1;
que.push(v);
}
}
}
return dis[t];
}
int dfs(int now, int left)//left: eesidual/剩余 flow
{
if(now == N || !left)
return left;
for(int &i = cur[now]; i; i = Edge[i].next)//Traverse all edges starting from s
{
int v = Edge[i].to, c = Edge[i].val;
if(c && dis[v] == dis[now] + 1)
{
int d = dfs(v, min(left, c));
if(d)
{
Edge[i].val -= d;
Edge[i^1].val += d;
return d;
}
}
}
return 0;
}
int Dinic(int s, int t)
{
int max_flow = 0;
while(bfs(s, t))
{
int val;
for(int i = 1; i < N+1; i++)
cur[i] = head[i];
while((val = dfs(s, INF)))
max_flow += val;
}
return max_flow;
}
int main()
{
int Case;
scanf("%d", &Case);
int ct = 1;
while (Case--)
{
memset(head, -1, sizeof(head));
cnt = 1;
scanf("%d%d", &N, &M);
int a, b, d;
for (int i = 1; i < M+1; i++)
{
scanf("%d%d%d", &a, &b, &d);
add_edge(a, b, d);
add_edge(b, a, 0);//construct the reverse edge
}
printf("Case %d: %d\n", ct, Dinic(1, N));
ct++;
}
return 0;
}
推送-重贴标签算法
在基于增广路径或线性规划的最大流问题的解中,非常适合
Hopcroft-Karp 二分匹配算法
目前最好的解决最大二分匹配问题的算法
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于