最大流模板(Maximum Flow)
一篇写得通俗易懂介绍最大流的文章:最大流模板【EdmondsKarp算法，简称EK算法，O(m^2n)】
残留网络
残存容量 cf(u, v) = c(u, v) - f(u, v);
算法导论中对残存网络的一些解释
一条边所能允许的反向流量最多将其正向流量抵消. 残存网络中的这些反向边允许算法将发送出来的流量发送回去. 而将流量从同一条边发送回去等同缩减该边流量.
Ford-Fulkerson方法
增广路径是残存网络中一条s到t的路径
残存容量是增广路径上能为每条边增加的流量的最大值
不断地沿着增广路径增加路径上的流量, 直到残存网络中不再有任何增广路时就找到了最大流.
代码模板
int map[SIZE][SIZE];
int pre[SIZE]; //记录前一个访问的节点
bool visited[SIZE];
int a[SIZE]; //可改进量
bool bfs(int s, int t, int n)
{
memset(a, 0, sizeof(a));
memset(visited, false, sizeof(visited));
queue<int> q;
q.push(s);
a[s] = INF;
visited[s] = true;
while (!q.empty())
{
int x = q.front();
q.pop();
for (int i = 0; i <= n; ++i) //todo
if (!visited[i] && map[x][i])
{
visited[i] = true;
pre[i] = x;
q.push(i);
a[i] = min(a[x], map[x][i]);
}
if (visited[t])
return true;
}
return false;
}
int maxFlow(int s, int t, int n)
{
int flow = 0;
while (bfs(s, t, n))
{
flow += a[t];
for (int i = t; i != s; i = pre[i])
{
map[pre[i]][i] -= a[t];
map[i][pre[i]] += a[t];
}
}
return flow;
}
