图论---最大流（Dinic）

最大流一定是阻塞流，阻塞流不一定是最大流。

阻塞流---从起点到终点的管道已经阻塞了。

• 时间复杂度：

  • 一般情况：O(n2m)O(n2m)（但实际运行效率较高，尤其在稀疏图上）。

  • 使用当前弧优化后，效率接近 O(nmlog⁡C)O(nmlogC)（CC 是最大容量）。

代码优化建议

1. 改用链式前向星（如边数 m > 1e5 时更高效）。

2. 预分配 vector 空间（如 v[a].reserve(10) 减少动态扩容开销）。

3. 改用 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;
}