图论---最大流（Dinic）
最大流一定是阻塞流，阻塞流不一定是最大流。
阻塞流---从起点到终点的管道已经阻塞了。
-
时间复杂度：
-
一般情况：O(n2m)O(n2m)（但实际运行效率较高，尤其在稀疏图上）。
-
使用当前弧优化后，效率接近 O(nmlogC)O(nmlogC)（CC 是最大容量）。
-
代码优化建议
-
改用链式前向星（如边数
m > 1e5时更高效）。 -
预分配
vector空间（如v[a].reserve(10)减少动态扩容开销）。 -
改用
int代替unsigned long long（除非题目明确要求大容量）。
-
省赛/ICPC：此代码足够应对大多数网络流题目（点数
n ≤ 500，边数m ≤ 1e4）。 -
更高阶优化：如需处理更大数据（如
n ≤ 1e5），需改用 ISAP 或 HLPP 算法。
步骤：1、BFS分层
2、DFS增广
#include<bits/stdc++.h>
using namespace std;#define int unsigned long long // 使用 unsigned long long 防止溢出
const int MN = 500; // 最大点数
const int INF = 0x3f3f3f3f; // 无穷大
int n, m, s, t; // 点数、边数、源点、汇点
int cur[MN], dep[MN]; // cur: 当前弧优化数组；dep: 层次深度
struct Node { int v, k, id; }; // 边的结构体：v=目标点，k=剩余容量，id=反向边索引
vector<Node> v[MN]; // 邻接表存图bool bfs() {queue<int> q;memset(dep, -1, sizeof(dep)); // 初始化 dep 为 -1dep[s] = 0; // 源点深度为 0q.push(s);while (!q.empty()) {int x = q.front();q.pop();for (int i = 0; i < v[x].size(); i++) {int y = v[x][i].v;int k = v[x][i].k;if (dep[y] == -1 && k > 0) { // 未访问过且剩余容量 > 0dep[y] = dep[x] + 1; // 更新深度q.push(y);}}}memset(cur, 0, sizeof(cur)); // 重置当前弧优化return dep[t] != -1; // 返回是否能到达汇点
}int dfs(int x, int ans) {if (x == t) return ans; // 到达汇点，返回当前流量for (int i = cur[x]; i < v[x].size(); i++) {int y = v[x][i].v;int k = v[x][i].k;int id = v[x][i].id;cur[x] = i; // 当前弧优化，避免重复访问if (dep[y] == dep[x] + 1 && k > 0) { // 必须在下一层且剩余容量 > 0int tmp = dfs(y, min(k, ans)); // 递归找增广路径if (tmp > 0) { // 找到可行流v[x][i].k -= tmp; // 更新正向边容量v[y][id].k += tmp; // 更新反向边容量return tmp;} else {dep[y] = -1; // 剪枝：该点无法到达汇点，标记为无效}}}return 0; // 无增广路径
}int dinic() {int ans = 0, tmp;while (bfs()) { // 只要还能分层（存在增广路径）while (tmp = dfs(s, INF)) { // 多路增广ans += tmp; // 累加流量}}return ans;
}void add(int a, int b, int k) {int sza = v[a].size(), szb = v[b].size();v[a].push_back({b, k, szb}); // 正向边v[b].push_back({a, 0, sza}); // 反向边（初始容量为 0）
}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n >> m >> s >> t;for (int i = 1; i <= m; i++) {int a, b, k;cin >> a >> b >> k;add(a, b, k); // 建图}cout << dinic(); // 计算最大流return 0;
}