最大流
题目要求:给出n点 m边 src sink 然后每条边有 u v capacity 求最大流
题目链接P3376 【模板】网络最大流
EK(Edmonds–Karp)算法:
\[\begin{align} & \color{Red}时间复杂度O(nm^2) \\ & \color{Red}空间复杂度O(n+m) \\ \end{align} \]#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define int long long
const int N = 6e5 + 9;
const int inf2 = 0x7f7f7f7f;
using namespace std;
#define int long long
#define ios std::ios::sync_with_stdio(false); std::cin.tie(0);
int n, m, src, sink;
int ans = 0; // 最大流量
int head[N];
int pre[N]; // 存储前驱边的数组 即连接节点u的上一条egde
struct node {
int to, capacity, next;
} e[N];
bool vis[N];
int idx = 1;
int dist[N]; // 存储从源节点到各节点的最短路径流量
int flag[2510][2510]; // 用于标记边的索引
void add(int u, int v, int val) {
// 添加正向边
e[++idx] = {v, val, head[u]};
head[u] = idx;
// 添加反向边
e[++idx] = {u, 0, head[v]};
head[v] = idx;
}
bool bfs() {
memset(vis, 0, sizeof vis); // 清空访问标记数组
dist[src] = inf2; // 初始化源节点的距离为无穷大
queue<int> q;
q.push(src);
vis[src] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; i != 0; i = e[i].next) {
int v = e[i].to;
int val = e[i].capacity;
// 如果边的容量为 0 或节点 v 已访问,跳过
if (e[i].capacity == 0 || vis[v]) continue;
vis[v] = 1;
pre[v] = i; // 记录前驱边
dist[v] = min(dist[u], val); // 流量只能取得最小的
q.push(v);
if (v == sink) // 到达sink,返回 true
return true;
}
}
return false; // 没有找到增广路径
}
void EK() {
int u = sink;
while (u != src) {
int mmin_stream = dist[sink]; // 当前增广路径的流量是整条路的最小值
int last = pre[u];
// 更新正向边的容量和反向边的容量
e[last].capacity -= mmin_stream;
e[last ^ 1].capacity += mmin_stream;
u = e[last ^ 1].to; // 更新 u 为反向边的终点
}
ans += dist[sink]; // 增加当前流量到总流量
}
void bd() {
cin >> n >> m >> src >> sink;
for (int i = 1; i <= m; ++i) {
int u, v, val;
cin >> u >> v >> val;
if (flag[u][v] == 0) {
add(u, v, val); // 添加边到图中
flag[u][v] = idx - 1; // 记录边的索引 因为dix起步时=1
}
else
e[flag[u][v]].capacity += val;
//存在多条边 容量加起来
}
}
signed main() {
ios;
bd();
while (bfs()) {
EK();
}
cout << ans; // 输出最大流量a
return 0;
}
标签:src,capacity,最大,val,int,网络,sink,dist,模板
From: https://www.cnblogs.com/Phrink734/p/18364773