题目链接：https://www.luogu.com.cn/problem/P3381
解题思路：完全来自 oi.wiki
代码对应我之前写的 最大流Dinic模板 + oi.wiki 上 基于dinic的修改。
示例程序：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 5, maxm = 1e5 + 5, inf = 0x3f3f3f3f;struct Edge {int v, w, c, nxt;
} edge[maxm];
int n, m, s, t, head[maxn], ecnt;void init() {ecnt = 0;fill(head+1, head+n+1, -1);
}void add_edge(int u, int v, int w, int c) {edge[ecnt] = { v, w, c, head[u] }; head[u] = ecnt++;edge[ecnt] = { u, 0, -c, head[v] }; head[v] = ecnt++;
}int dis[maxn], cur[maxn], sum_cost;
bool vis[maxn];bool spfa() {queue<int> que;fill(dis, dis+n+1, inf);dis[s] = 0;vis[s] = true;que.push(s);while (!que.empty()) {int u = que.front();que.pop();vis[u] = false;for (int i = head[u]; ~i; i = edge[i].nxt) {auto &[v, w, c, nxt] = edge[i];if (w > 0 && dis[u] + c < dis[v]) {dis[v] = dis[u] + c;if (!vis[v]) {vis[v] = true;que.push(v);}}}}return dis[t] < inf;
}int dfs(int u, int flow) {if (u == t)return flow;vis[u] = true;int ans = 0;for (int &i = cur[u]; ~i && ans < flow; i = edge[i].nxt) {auto &[v, w, c, nxt] = edge[i];if (!vis[v] && w > 0 && dis[v] == dis[u] + c) {int f = dfs(v, min(w, flow - ans));if (f > 0) {ans += f;sum_cost += f * c;edge[i].w -= f;edge[i^1].w += f;}}}vis[u] = false;return ans;
}int dinic() {int ans = 0;while (spfa()) {copy(head+1, head+n+1, cur+1);int f = dfs(s, inf);ans += f;}return ans;
}int main() {cin >> n >> m >> s >> t;init();for (int i = 0, u, v, w, c; i < m; i++) {cin >> u >> v >> w >> c;add_edge(u, v, w, c);}int max_flow = dinic();cout << max_flow << " " << sum_cost << "\n";return 0;
}