网站建设财务计划与预测,软件开发学院,手机上网站用建设工具,鞍山市城乡建设局网站算法进阶课整理
CSDN个人主页#xff1a;更好的阅读体验 原题链接
题目描述
给定一个包含 n n n 个点 m m m 条边的有向图#xff0c;并给定每条边的容量#xff0c;边的容量非负。
图中可能存在重边和自环。求从点 S S S 到点 T T T 的最大流。
输入格式
第一行包…算法进阶课整理
CSDN个人主页更好的阅读体验 原题链接
题目描述
给定一个包含 n n n 个点 m m m 条边的有向图并给定每条边的容量边的容量非负。
图中可能存在重边和自环。求从点 S S S 到点 T T T 的最大流。
输入格式
第一行包含四个整数 n , m , S , T n,m,S,T n,m,S,T。
接下来 m m m 行每行三个整数 u , v , c u,v,c u,v,c表示从点 u u u 到点 v v v 存在一条有向边容量为 c c c。
点的编号从 1 1 1 到 n n n。
输出格式
输出点 S S S 到点 T T T 的最大流。
如果从点 S S S 无法到达点 T T T 则输出 0 0 0。
数据范围 2 ≤ n ≤ 10000 2 \le n \le 10000 2≤n≤10000, 1 ≤ m ≤ 100000 1 \le m \le 100000 1≤m≤100000, 0 ≤ c ≤ 10000 0 \le c \le 10000 0≤c≤10000, S ≠ T S \neq T ST 算法步骤
Dinic 算法其实是 EK 算法的一个暴力的优化EK 算法每次只能搜索一条增广路径而 Dinic 算法每次都用 DFS 的形式尽可能多的搜索增广路径。
而图中可能存在环为了保证 DFS 的过程中不会造成死循环这里可以使用分层图这样每次都是一层一层往下搜索就不会出现死循环。
BFS 建立分层图DFS 找出所有能增广的路径累加最大流量
注意 Dinic 算法对于优化非常敏感如果优化的不好就可能直接 TLE
算法时间复杂度 O ( n 2 m ) O(n^2m) O(n2m)
AC Code C \text{C} C #include iostream
#include cstringusing namespace std;const int N 10010, M 200010;
const int INF 1e9;int n, m, S, T;
int h[N], e[M], ne[M], f[M], idx;
int d[N], q[N], cur[N];
// d[] 存分层图中每个点的深度
// q[] 手写队列
// cur[] 当前弧优化inline void add(int a, int b, int c)
{e[idx] b, f[idx] c, ne[idx] h[a], h[a] idx ; // 正向边e[idx] a, f[idx] 0, ne[idx] h[b], h[b] idx ; // 反向边用于反悔
}bool bfs()
{memset(d, -1, sizeof d); // 记得初始化int hh 0, tt 0;q[0] S, d[S] 0, cur[S] h[S];// 将源点加入队列源点深度为0初始化源点当前弧为表头while (hh tt){int t q[hh ];for (int i h[t]; ~i; i ne[i]){int j e[i];if (d[j] -1 f[i]) // 存在增广路才能从这里分层{d[j] d[t] 1; // 更新深度cur[j] h[j]; // 所有点当前弧最开始都是表头if (j T) return true; // 如果找到汇点了就说明有增广路q[ tt] j;}}}return false; // 没有增广路
}int find(int u, int lim) // DFSu是当前点lim是u之前的路径能流过的最大值
{if (u T) return lim; // 如果已经流到汇点了就返回这个最大值int flow 0; // 当前往下流的流量for (int i cur[u]; ~i flow lim; cur[u] i, i ne[i])// 注意应从当前弧开始遍历并且每次要更新。没有剩余流量也应该退出{int j e[i];if (d[j] d[u] 1 f[i])// 按分层图遍历防止死循环{int t find(j, min(f[i], lim - flow));// 找到后面能流的最大值if (!t) d[j] -1;// 如果没有流量那么说明后面没有增广路了这个点不会用到将深度设为-1f[i] - t, f[i ^ 1] t, flow t;// 当前边减流量反向边加流量实际流量加流量}}return flow;
}int dinic()
{int r 0, flow 0;while (bfs()) while ((flow find(S, INF))) r flow;// 只要存在增广路就一直DFS直到DFS出的流量为0return r;
}int main()
{int a, b, c;memset(h, -1, sizeof h);scanf(%d%d%d%d, n, m, S, T);while (m -- ){scanf(%d%d%d, a, b, c);add(a, b, c);}printf(%d\n, dinic());return 0;
}最后如果觉得对您有帮助的话点个赞再走吧
