最大流
网络流中最常见的问题就是网络最大流。假定从源点流出的流量足够多,求能够流入汇点的最大流量。解决这个问题最常用的是Ford-Fulkerson算法及其优化。
洛谷模板:https://www.luogu.com.cn/problem/P3376
DFS
用dfs实现的FF算法时间复杂度上界是 O(ef) ,其中 e 为边数,f为最大流。
int n, m, s, t; // s是源点,t是汇点
bool vis[MAXN];
int dfs(int p = s, int flow = INF)
{
if (p == t)
return flow; // 到达终点,返回这条增广路的流量
vis[p] = true;
for (int eg = head[p]; eg; eg = edges[eg].next)
{
int to = edges[eg].to, vol = edges[eg].w, c;
// 返回的条件是残余容量大于0、未访问过该点且接下来可以达到终点(递归地实现)
// 传递下去的流量是边的容量与当前流量中的较小值
if (vol > 0 && !vis[to] && (c = dfs(to, min(vol, flow))) != -1)
{
edges[eg].w -= c;
edges[eg ^ 1].w += c;
// 这是链式前向星取反向边的一种简易的方法
// 建图时要把cnt置为1,且要保证反向边紧接着正向边建立
return c;
}
}
return -1; // 无法到达终点
}
inline int FF()
{
int ans = 0, c;
while ((c = dfs()) != -1)
{
memset(vis, 0, sizeof(vis));
ans += c;
}
return ans;
}
Edmond-Karp算法
其实,EK算法就是BFS实现的FF算法。
#include<bits/stdc++.h>
//#define LOCAL
#define sum(a) ( accumulate ((a).begin(), (a).end(), 0int))
#define mine(a) (*min_element((a).begin(), (a).end()))
#define maxe(a) (*max_element((a).begin(), (a).end()))
#define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin())
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
#define print(x) cout<<(x)<<'\n'
#define print_v(x) for (int iii = 0; iii < (x).size() - 1; ++iii) {cout << (x)[iii] << ' ';}cout << (x)[(x).size() - 1]<< '\n'
using namespace std;
#define mp make_pair
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 5e5 + 5;
int vis[MAXN], inqueue[MAXN];
int head[MAXN];
int cnt = 2;
int n, m, s, t;
int source, sink;
struct Edge {
int from, to, w, next;
} edges[MAXN];
void add(int u, int v, int w) {//添加一条边u--v
edges[cnt].to = v;
edges[cnt].w = w;
edges[cnt].next = head[u];
head[u] = cnt++;
}
int last[MAXN], flow[MAXN];
inline int bfs() {
memset(last, -1, sizeof(last));
queue<int> q;
q.push(s);
flow[s] = inf;
while (!q.empty()) {
int p = q.front();
q.pop();
if (p == t) // 到达汇点,结束搜索
break;
for (int eg = head[p]; eg; eg = edges[eg].next) {
int to = edges[eg].to, vol = edges[eg].w;
if (vol > 0 && last[to] == -1) // 如果残余容量大于0且未访问过(所以last保持在-1)
{
last[to] = eg;
flow[to] = min(flow[p], vol);
q.push(to);
}
}
}
return last[t] != -1;
}
inline int EK() {
int maxflow = 0;
while (bfs()) {
maxflow += flow[t];
for (int i = t; i != s; i = edges[last[i] ^ 1].to) // 从汇点原路返回更新残余容量
{
edges[last[i]].w -= flow[t];
edges[last[i] ^ 1].w += flow[t];
}
}
return maxflow;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("output.txt", "w", stdout);
freopen("input.txt", "r", stdin);
#endif
cin >> n >> m >> s >> t;
for (int i = 1; i <= m; ++i) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, 0);
}
print(EK());
}
它的复杂度上限是 O(ve2) ,其中 v 为点数。
Dinic算法
然而,最常用的网络流算法是Dinic算法。作为FF/EK算法的优化,它选择了先用BFS分层,再用DFS寻找。它的时间复杂度上界是 O(ev2) 。
#include<bits/stdc++.h>
//#define LOCAL
#define sum(a) ( accumulate ((a).begin(), (a).end(), 0int))
#define mine(a) (*min_element((a).begin(), (a).end()))
#define maxe(a) (*max_element((a).begin(), (a).end()))
#define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin())
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
#define print(x) cout<<(x)<<'\n'
#define print_v(x) for (int iii = 0; iii < (x).size() - 1; ++iii) {cout << (x)[iii] << ' ';}cout << (x)[(x).size() - 1]<< '\n'
using namespace std;
#define mp make_pair
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 5e5 + 5;
int vis[MAXN], inqueue[MAXN];
int head[MAXN];
int cnt = 2;
int n, m, s, t;
int source, sink;
struct Edge {
int from, to, w, next;
} edges[MAXN];
void add(int u, int v, int w) {//添加一条边u--v
edges[cnt].to = v;
edges[cnt].w = w;
edges[cnt].next = head[u];
head[u] = cnt++;
}
int lv[MAXN], cur[MAXN]; // lv是每个点的层数,cur用于当前弧优化标记增广起点
inline bool bfs() // BFS分层
{
memset(lv, -1, sizeof(lv));
lv[s] = 0;
memcpy(cur, head, sizeof(head)); // 当前弧优化初始化
queue<int> q;
q.push(s);
while (!q.empty()) {
int p = q.front();
q.pop();
for (int eg = head[p]; eg; eg = edges[eg].next) {
int to = edges[eg].to, vol = edges[eg].w;
if (vol > 0 && lv[to] == -1)
lv[to] = lv[p] + 1, q.push(to);
}
}
return lv[t] != -1; // 如果汇点未访问过说明已经无法达到汇点,此时返回false
}
int dfs(int p = s, int flow = inf) {
if (p == t)
return flow;
int rmn = flow; // 剩余的流量
for (int eg = cur[p]; eg && rmn; eg = edges[eg].next) // 如果已经没有剩余流量则退出
{
cur[p] = eg; // 当前弧优化,更新当前弧
int to = edges[eg].to, vol = edges[eg].w;
if (vol > 0 && lv[to] == lv[p] + 1) // 往层数高的方向增广
{
int c = dfs(to, min(vol, rmn)); // 尽可能多地传递流量
rmn -= c; // 剩余流量减少
edges[eg].w -= c; // 更新残余容量
edges[eg ^ 1].w += c; // 再次提醒,链式前向星的cnt需要初始化为1(或-1)才能这样求反向边
}
}
return flow - rmn; // 返回传递出去的流量的大小
}
int dinic() {
int ans = 0;
while (bfs())
ans += dfs();
return ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("output.txt", "w", stdout);
freopen("input.txt", "r", stdin);
#endif
cin >> n >> m >> s >> t;
for (int i = 1; i <= m; ++i) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, 0);
}
print(dinic());
}
最后更新于