Day4 网络流与二分图

之前那篇博客是在入门网络流时写的，现在对网络流重新有了一定的理解。

1. 最大流

FF 增广思想

Ford–Fulkerson 增广，核心即不断找增广路并增广。

dfs 实现

// FF brute
#include <bits/stdc++.h>
#define int long longusing namespace std;int n, m, s, t, r[205][205], ans;bool vis[205];
int dfs(int u, int sum) // sum：流入 u 的流量
{if(sum == 0 or u == t) return sum;vis[u] = true;int flow = 0;for(int i=1; i<=n; i++){if(!vis[i] and r[u][i] > 0){//找 u 到 t 路上的最小限制并增广int d = dfs(i, min(sum, r[u][i]));r[u][i] -= d, r[i][u] += d;flow += d, sum -= d;}}return flow;
}signed main()
{cin >> n >> m >> s >> t;for(int i=1; i<=m; i++){int u, v, w;cin >> u >> v >> w;r[u][v] += w;}int d;while(d = dfs(s, 1e9)) {memset(vis, 0, sizeof(vis));ans += d;}cout << ans;
}

这种方法的复杂度与最大流 $f$ 有关，至多执行 $f$ 轮 dfs，时间复杂度 $O (n f)$ 。

bfs 实现 / EK

FF 增广的 bfs 实现也称 EK 算法。

// FF EK#include <bits/stdc++.h>
#define int long longusing namespace std;int n, m, s, t, r[205][205], ans, d[205], pre[205];
queue <int> q;
bool bfs()
{memset(d, 0, sizeof(d)); memset(pre, 0, sizeof(pre));d[s] = 1, q.push(s); while(!q.empty()){int u = q.front(); q.pop();for(int i=1; i<=n; i++)if(d[i] == 0 and r[u][i] > 0)pre[i] = u, d[i] = d[u] + 1, q.push(i);}return d[t];
}int augment()
{int flow = 1e9;for(int a=t; a!=s; a=pre[a]) flow = min(flow, r[pre[a]][a]);for(int a=t; a!=s; a=pre[a]) r[pre[a]][a] -= flow, r[a][pre[a]] += flow;return flow;
}signed main()
{cin >> n >> m >> s >> t;for(int i=1; i<=m; i++){int u, v, w;cin >> u >> v >> w;r[u][v] += w;}while(bfs()) ans += augment();cout << ans;
}

EK 算法的时间复杂度是 $O(nm^2)$ 。

证明：每条边至多做 $\dfrac n 2$ 次增广路上的关键边。
OI-wiki

Dinic

通过 bfs 对图分层标记，每次 dfs 只访问下一层的结点。
同时加上当前弧优化，即不重复访问满流边，维护第一条有必要尝试的边。

// dinic#include <bits/stdc++.h>
#define int long longusing namespace std;struct Edge{int nxt, to, r;
}e[10005];int tot = 1, head[205];
void add_edge(int u, int v, int w)
{e[++tot] = {head[u], v, w};head[u] = tot;
}int n, m, s, t, ans, d[205], cur[205];queue <int> q;
bool bfs()
{memset(d, 0, sizeof(d)); d[s] = 1, q.push(s); while(!q.empty()){int u = q.front(); q.pop();for(int i=head[u]; i; i=e[i].nxt){int v = e[i].to;if(d[v] == 0 and e[i].r > 0)d[v] = d[u] + 1, q.push(v);}}return d[t];
}int dfs(int u, int sum)
{if(sum == 0 or u == t) return sum;int flow = 0;for(int i=cur[u]; i; i=e[i].nxt){cur[u] = i;int v = e[i].to;if(d[v] == d[u] + 1 and e[i].r > 0){int d = dfs(v, min(sum, e[i].r));e[i].r -= d, e[i^1].r += d;flow += d, sum -= d;}}return flow;
}signed main()
{cin >> n >> m >> s >> t;for(int i=1; i<=m; i++){int u, v, w;cin >> u >> v >> w;add_edge(u, v, w);add_edge(v, u, 0);}while(bfs()) {for(int i=1; i<=n; i++) cur[i] = head[i];ans += dfs(s, 1e9);}cout << ans;
}

2. 二分图最大匹配

二分图：对于 $G (V, E)$ ，分成两个点集 $V 1, V 2$ ，对于所有的 $\in E$ ，保证 $u, v$ 属于不同点集。

容易发现二分图中不存在奇环。
二分图的匹配：选定一些边，这些边之间没有公共点。

建网络流模型即可，通过虚拟源点和虚拟汇点限制 $1$ 。

如果要输出方案，可以通过 $f (u, v) < c (u, v)$ 判断。如果根据残量网络，需要根据反向边的残量网络判断。

#include <bits/stdc++.h>
using namespace std;int n, m, s, t, r[105][105], ans, d[105], cur[105];
queue <int> q;
bool bfs()
{memset(d, 0, sizeof(d)); d[s] = 1, q.push(s); while(!q.empty()){int u = q.front(); q.pop();for(int i=1; i<=n+2; i++)if(d[i] == 0 and r[u][i] > 0)d[i] = d[u] + 1, q.push(i);}return d[t];
}int dfs(int u, int sum)
{if(sum == 0 or u == t) return sum;int flow = 0;for(int v=cur[u]; v<=n+2; v++){cur[u] = v;if(d[v] == d[u] + 1 and r[u][v] > 0){int d = dfs(v, min(sum, r[u][v]));r[u][v] -= d, r[v][u] += d;flow += d, sum -= d;}}return flow;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> m >> n;s = n+1, t = n+2;while(1){int u, v;cin >> u >> v;if(u == -1 and v == -1) break;r[u][v] = 1;}for(int i=1; i<=m; i++) r[s][i] = 1;for(int i=m+1; i<=n; i++) r[i][t] = 1;while(bfs()) {for(int i=1; i<=n+2; i++) cur[i] = 1;ans += dfs(s, 1e9);}cout << ans << "\n";for(int u=1; u<=m; u++){for(int v=m+1; v<=n; v++){if(r[v][u]) cout << u << " " << v << "\n";}}	return 0;
}