```cpp
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define fir first
#define sec second
#define int long long
const int N = 5e3 + 5, M = 1e5 + 5, INf = 0x3f3f3f3f3f3f3f3f;
struct NetWork {
int st, ed;
private:
const int INF = 0x3f3f3f3f3f3f3f3f;
int dist[N], cur[N];
int head[N], idx = 1;
bool vis[N];
int incf[N], pre[N];
queue<int> q;
struct Edge {
int to, val, nxt, len;
} e[M];
bool bfs() {
memset(dist, 0, sizeof dist);
dist[st] = 1;
while(q.size()) {
q.pop();
}
q.push(st);
while(q.size()) {
int t = q.front(); q.pop();
for(int it = head[t]; it; it = e[it].nxt) {
Edge &i = e[it];
if(!i.val || dist[i.to]) {
continue;
}
dist[i.to] = dist[t] + 1;
q.push(i.to);
if(i.to == ed) {
return 1;
}
}
}
return 0;
}
bool spfa() {
memset(dist, 0x3f, sizeof dist),
memset(vis, 0, sizeof vis);
dist[st] = 0, vis[st] = 1;
incf[st] = INF;
while(q.size()) {
q.pop();
}
q.push(st);
while(q.size()) {
int t = q.front(); q.pop();
vis[t] = 0;
for(int it = head[t]; it; it = e[it].nxt) {
Edge &i = e[it];
if(!i.val) {
continue;
}
if(dist[i.to] > dist[t] + i.len) {
dist[i.to] = dist[t] + i.len;
incf[i.to] = min(incf[t], i.val);
pre[i.to] = it;
// cout << i.to << " " << it << endl;
if(!vis[i.to]) {
q.push(i.to);
vis[i.to] = 1;
}
if(i.to == ed) {
return 1;
}
}
}
}
return 0;
}
int dfs(int x, int flow) {
if(x == ed) {
return flow;
}
int res = 0;
for(int it = cur[x]; it; it = e[it].nxt) {
Edge &i = e[it], &j = e[it ^ 1];
cur[x] = it;
if(dist[i.to] == dist[x] + 1 && i.val) {
int t = dfs(i.to, min(flow, i.val));
if(t == 0) {
dist[i.to] = 0;
}
i.val -= t, j.val += t;
res += t, flow -= t;
if(flow == 0) {
break;
}
}
}
if(res == 0) {
dist[x] = 0;
}
return res;
}
int Dinic() {
int res = 0;
while(bfs()) {
memcpy(cur, head, sizeof head);
res += dfs(st, INF);
}
return res;
}
public:
void init() {
idx = 1;
memset(head, 0, sizeof head),
memset(cur, 0, sizeof cur);
}
void addEdge(int x, int y, int w, int l) {
e[++ idx] = {y, w, head[x], l};
head[x] = idx;
e[++ idx] = {x, 0, head[y], -l};
head[y] = idx;
}
int maxFlow() {
return Dinic();
}
int minCut() {
return Dinic();
}
pair<int, int> minVal() {
int mxf = 0, mnc = 0;
while(spfa()) {
mxf += incf[ed], mnc += dist[ed] * incf[ed];
int p = ed;
while(p != st) {
// cout << p << endl;
e[pre[p]].val -= incf[ed],
e[pre[p] ^ 1].val += incf[ed];
p = e[pre[p] ^ 1].to;
}
}
return {mxf, mnc};
}
} nw;
int n, m, s, t;
signed main() {
cin >> n >> m >> s >> t;
nw.st = s, nw.ed = t;
for(int i = 1, x, y, f, l; i <= m; i ++) {
cin >> x >> y >> f >> l;
nw.addEdge(x, y, f, l);
}
pii ans = nw.minVal();
return cout << ans.fir << " " << ans.sec << endl, 0;
}
```
by Wiales_Pretharp @ 2024-01-12 21:13:27
目前是 #1~7 AC，#8,10,11 WA & #9 TLE
by Wiales_Pretharp @ 2024-01-12 21:15:03
```c++
dist[i.to] = dist[t] + i.len;
```
```c++
dist[i.to] == dist[x] + 1
```
阿巴。
另外最短路图并不一定是个 DAG，里面可以有零环，如果不打 `vis` 那这个是指数级的。
再另外（单纯的）多路增广费用流并不会比单路增广复杂度更优，实际上费用值域稍大就变成纯增加常数了。
by reveal @ 2024-01-12 21:39:38
@[reveal](/user/523491) 有没有这么一种可能，我写的是 spfa，bfs 是封装的产物。
by Wiales_Pretharp @ 2024-01-12 21:49:18
@[Wiales_Pretharp](/user/612663)
```c++
if(i.to == ed) {
return 1;
}
```
最短路也退，这么会退出优化。
by reveal @ 2024-01-12 21:58:05
@[reveal](/user/523491) upd，能想到的错误都已经改了，后面发现是 pre 那里的回溯莫名出错
不过总归还是感谢您的帮助！
by Wiales_Pretharp @ 2024-01-12 23:55:07