2023年7月30日发(作者：)

费⽤流模板#include#include#include#include#include#includeusing namespace std;const int maxn = 1e5 + 10;struct node{ int next, to, flow, cost;};node edge[maxn];int head[maxn], flow[maxn], pre[maxn], dist[maxn], last[maxn];int n, m, st, en;int tot;bool vis[maxn];void add(int u, int v, int w, int c){ edge[tot] = (node){head[u], v, w, c}; head[u] = tot++; edge[tot] = (node){head[v], u, 0, -c}; head[v] = tot++;}bool spfa(){ memset(flow, 0x3f, sizeof(flow)); memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); queueQ; (st); vis[st] = true; dist[st] = 0; pre[en] = -1; while(!()) { int now = (); (); vis[now] = 0; for(int i = head[now]; i != -1; i = edge[i].next) { if(edge[i].flow > 0 && dist[edge[i].to] > dist[now] + edge[i].cost) { dist[edge[i].to] = dist[now] + edge[i].cost; pre[edge[i].to] = now; last[edge[i].to] = i; flow[edge[i].to] = min(flow[now], edge[i].flow); if(!vis[edge[i].to]) { vis[edge[i].to] = true; (edge[i].to); } } } } //printf("%dn", 1322333); return pre[en] != -1;}}void mcmf(){ long long mcost = 0, mflow = 0; while(spfa()) { mflow += flow[en]; mcost += dist[en] * flow[en]; int now = en; while(now != st) { edge[last[now]].flow -= flow[en]; edge[last[now]^1].flow += flow[en]; now = pre[now]; } //printf("%dn", 1321); } printf("%lld %lldn", mflow ,mcost);}int main(){ tot = 0; memset(head, -1, sizeof(head)); scanf("%d%d%d%d", &n, &m, &st, &en); for(int i = 0; i < m; i++) { int u, v ,w, c; scanf("%d%d%d%d", &u, &v, &w, &c); add(u, v, w, c); } mcmf(); return 0;}补充⼀个dinic的， 不过可能有点问题，加上当前弧优化居然t了，也没找出来哪⾥错了#include#include#include#include#include#include#pragma GCC optimize(2)using namespace std;const int maxn = 1e5 + 10;struct node{ int next, to, flow, cost;};long long mcost = 0, mflow = 0;node edge[maxn];int head[maxn], flow[maxn], pre[maxn], dist[maxn], last[maxn], cur[maxn];int n, m, st, en;int tot;bool vis[maxn];void add(int u, int v, int w, int c){ edge[tot] = (node){head[u], v, w, c}; head[u] = tot++; edge[tot] = (node){head[v], u, 0, -c}; edge[tot] = (node){head[v], u, 0, -c}; head[v] = tot++;}bool spfa(){ memset(flow, 0x3f, sizeof(flow)); memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); queueQ; (st); vis[st] = true; dist[st] = 0; while(!()) { int now = (); (); vis[now] = 0; for(int i = head[now]; i != -1; i = edge[i].next) { if(edge[i].flow > 0 && dist[edge[i].to] > dist[now] + edge[i].cost) { dist[edge[i].to] = dist[now] + edge[i].cost; flow[edge[i].to] = min(flow[now], edge[i].flow); if(!vis[edge[i].to]) { vis[edge[i].to] = true; (edge[i].to); } } } } //printf("%dn", 1322333); return dist[en] != 0x3f3f3f3f;}int dfs(int u, int flow){ if(u == en) { mflow += flow; return flow; } int f = 0; vis[u] = true; for(int i = head[u]; ~i; i = edge[i].next) { //cur[u] = i; if(!vis[edge[i].to] && dist[edge[i].to] == dist[u] + edge[i].cost){ int w = dfs(edge[i].to, min(edge[i].flow, flow - f)); f += w; edge[i].flow -= w, edge[i ^ 1].flow += w; mcost += edge[i].cost * w; if(flow == f) break; } } vis[u] = false; return f;}void mcmf(){ while(spfa()) { dfs(st, 0x3f3f3f3f); //printf("%dn", 1321); } printf("%lld %lldn", mflow ,mcost);}int main(){ tot = 0; memset(head, -1, sizeof(head)); scanf("%d%d%d%d", &n, &m, &st, &en); for(int i = 0; i < m; i++) { int u, v ,w, c; scanf("%d%d%d%d", &u, &v, &w, &c); add(u, v, w, c); } mcmf(); return 0;}