如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。
输入输出格式
输入格式：
第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi）
输出格式：
一行，包含一个正整数，即为该网络的最大流。
Dinic（当前点优化 + 当前边优化） #include <bits/stdc++.h> using namespace std; const int maxn = 1e4 + 5; const int maxm = 1e6 + 5; const int inf = 2e9 + 5; int cur[maxn]; int head[maxn], dep[maxn]; int tot, n, m; struct Edge { int u, v, w, next; }edge[maxm]; inline void init() { memset(head, -1, sizeof(head)); tot = 1; } inline void add(int u, int v, int w) { edge[++tot].u = u; edge[tot].v = v; edge[tot].w = w; edge[tot].next = head[u]; head[u] = tot; } inline int bfs(int s, int t) { for(int i = 0; i <= n; i++) { dep[i] = inf; } queue<int> q; q.push(s); dep[s] = 0; while(!q.empty()) { int u = q.front(); q.pop(); for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if(edge[i].w > 0 && dep[u] + 1 < dep[v]) { dep[v] = dep[u] + 1; if(v == t) return 1; //当前点优化 q.push(v); } } } return dep[t] != inf; } inline int dfs(int u, int t, int flow) { if(u == t) { return flow; } int res = 0; for(int i = cur[u]; i != -1; i = edge[i].next) { cur[u] = i; //当前边优化 int w = edge[i].w; int v = edge[i].v; if(w <= 0 || dep[v] != dep[u] + 1) { continue; } res = dfs(v, t, min(flow, w)); if(res > 0) { edge[i].w -= res; edge[i ^ 1].w += res; return res; } } return -1; } inline int Dinic(int s, int t) { int ans = 0, ret; while(bfs(s, t)) { for(int i = 0; i <= n; i++) { cur[i] = head[i]; } while((ret = dfs(s, t, inf)) != -1) { ans += ret; } } return ans; } inline int read() { int ans = 0; char ch = getchar(); while(ch < '0' || ch > '9') { ch = getchar(); } while(ch >= '0' && ch <= '9') { ans = ans * 10 + ch - '0'; ch = getchar(); } return ans; } int main() { int u, v, w, s, t; init(); n = read(); m = read(); s = read(); t = read(); for(int i = 1; i <= m; i++) { u = read(); v = read(); w = read(); add(u, v, w); add(v, u, 0); } cout << Dinic(s, t) << endl; return 0; }
