题目传送门
题目描述
如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。
输入格式
第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi）
输出格式
一行，包含一个正整数，即为该网络的最大流。
输入
4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40
输出
50
说明/提示
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=10，M<=25
对于70%的数据：N<=200，M<=1000
对于100%的数据：N<=10000，M<=100000
样例说明：
题目中存在3条路径：
4–>2–>3，该路线可通过20的流量
4–>3，可通过20的流量
4–>2–>1–>3，可通过10的流量（边4–>2之前已经耗费了20的流量）
故流量总计20+20+10=50。输出50。
题解
- 网络流最大流模板题
AC-Code
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 7;
int n, m;struct Edge {
int to;int next;int val;
}edge[maxn << 1]; // 双向边，开 2 倍数组
int head[maxn];
int cnt; // 边的数量，从 0 开始编号
int depth[maxn]; // 分层图标记深度
int cur[maxn]; // 当前弧优化，记录当前点 u 循环到了哪一条边
void add(int u, int v, int w) {
edge[cnt].to = v;edge[cnt].next = head[u];edge[cnt].val = w;head[u] = cnt++;
}// bfs分层图
bool bfs(int s, int t) {
queue<int>q;memset(depth, 0, sizeof depth);depth[s] = 1; // 源点深度为 1cur[s] = head[s];q.push(s);while (!q.empty()) {
int u = q.front();q.pop();for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;if (edge[i].val > 0 && depth[v] == 0) {
// 如果残量不为0，且 v 还未分配深度depth[v] = depth[u] + 1;cur[v] = head[v]; //------当前弧优化，注意在bfs里，这样做到了“按需赋值”，因为Dinic本来上界就松得一匹, BFS的过程中不连通的点根本就不用再管了...if (v == t) // -----分层图汇点优化：遇到汇点直接返回------return true;q.push(v);}}}return depth[t]; // 汇点深度为 0：不存在分层图，返回false；// 非 0 ：存在增广路，返回true
}// dfs寻找增广路
int dfs(int u, int flow, int t) {
if (u == t || flow <= 0) // 到达汇点return flow;int rest = flow;for (int i = cur[u]; ~i; i = edge[i].next) {
int v = edge[i].to;if (depth[v] == depth[u] + 1 && edge[i].val != 0) {
// 满足分层图、残量>0 两个条件int k = dfs(v, min(rest, edge[i].val), t); // 向下增广if (k < 0) // ------无用点优化-----depth[v] = 0;rest -= k;edge[i].val -= k; // 正向边减edge[i ^ 1].val += k; // 反向边加if (rest <= 0) //------剩余量优化：在进行增广的时候，如果该节点已经没有流量，直接退出------break;}}return flow - rest; // flow：推送量，rest：淤积量，flow - rest：接受量/成功传递量
}
int Dinic(int s, int t) {
int ans = 0;while (bfs(s, t)) {
ans += dfs(s, inf, t);}return ans;
}int main() {
ios;int s_, t_;while (cin >> n >> m >> s_ >> t_) {
::cnt = 0;memset(head, -1, sizeof head);for (int i = 1, a, b, c; i <= m; i++) {
cin >> a >> b >> c;add(a, b, c);add(b, a, 0);}cout << Dinic(s_, t_) << endl;}
}