分析
记(D_i)为(S)到(i)的最短路，那么对于所有边((i,j))，都要满足(D_i+cost_{i,j}geq D_j)。
我们考虑普通的费用流，它的原理是沿着一条(S ightarrow T)的最短路径满足增广，显然对于这条路径上的所有边((i,j))，都是满足(D_i+cost_{i,j}=D_j)的。
原图上我们对于(forall v)，(exists u)，满足(D_u+cost_{u,v}=D_v)，但是我们增广过后这种边就不一定存在。
我们的处理方法是再跑一遍最短路进行增广，那这样子每次只会增广一条路，而ZKW费用流可以进行多路增广解决此问题。
做法
假设我们一开始的边权均(geq 0)，定义(D[1...n])为每个点的顶标（一开始均为(0)），而对于这个顶标我们需要满足条件和上面最短路的条件一样。
我们沿着顶标满足((i,j),D_i+cost_{i,j}=D_j)的边增广。
那么当某个时刻我们不存在(S ightarrow T)的流时，记我们这次访问的点集为(V)。
(Delta=min_limits{iin V,j otin V,u(i,j)} D_i+cost_{i,j}-D_j)，然后我们将所有(iin V)的(D_i)减去(Delta)，
这样子可以保证有一条边满足(D_i+cost_{i,j}-D_j=Delta)，那么我们就可以继续向我们没有访问过的点集增广了。
因为每次减去(Delta)时它肯定是花费最小代价可以沟通的点，那么一次增广的答案就是(-D_S imes)流量。
一些注意事项
可以注意到因为你要满足最短路的定义所以如果有边权(< 0)时顶标一开始全部设为(0)不满足条件，那么你可以想到一开始将(D)全部设为(S)到每个点的最短路。
那么又出现了一个问题，你每次贡献应该是加在(S)上，但是这样子的话就变为了在(T)上。
所以我们一开始改用一遍(spfa)跑由(T)开始沿反向边的最短路，那么可以跑出每个点到(T)的最短距离(D_i)。
那么满足(D_v+cost_{u,v}geq D_u)，增广的条件也由之变为(D_v+cost_{u,v}=D_uLeftrightarrow D_v+cost_{u,v}-D_u=0)，还是考虑可以访问到的点集(V)，
那么这次就是对于(forall iin V)，(D_i)加上(Delta=min_limits{iin V,j otin V,u(i,j)} D_j+cost_{i,j}-D_i)，这样才能继续增广。
这样子的话答案就还是(D_S imes)流量（注意此时(D_S>0)）。
发现如果边权全为正时先跑一遍(spfa)会快许多，那么索性所有情况都按照初始时有负权的情况跑算了（大雾
代码实现
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <queue>
using namespace std;
const int INF = 1e9;
const int MAX_N = 1e4 + 5;
struct Graph { int to, cap, cost, next; } e[MAX_N * 100];
int fir[MAX_N], e_cnt;
void clearGraph() { memset(fir, -1, sizeof(fir)); e_cnt = 0; }
void Add_Edge(int u, int v, int c, int w) {
e[e_cnt] = (Graph){v, c, w, fir[u]}, fir[u] = e_cnt++;
e[e_cnt] = (Graph){u, 0, -w, fir[v]}, fir[v] = e_cnt++;
}
int N, M, S, T, dis[MAX_N];
bool inq[MAX_N];
bool spfa() {
queue<int> que;
for (int i = 0; i <= N; i++) dis[i] = INF;
dis[T] = 0, inq[T] = 1, que.push(T);
while (!que.empty()) {
int x = que.front(); que.pop();
for (int i = fir[x]; ~i; i = e[i].next) {
int v = e[i].to, w = e[i ^ 1].cost;
if (e[i ^ 1].cap && dis[v] > dis[x] + w) {
dis[v] = dis[x] + w;
if (!inq[v]) que.push(v), inq[v] = 1;
}
}
inq[x] = 0;
}
return dis[S] != INF;
}
int tim, vis[MAX_N];
bool relabel() {
int res = INF;
for (int x = 0; x <= N; x++) {
if (vis[x] != tim) continue;
for (int i = fir[x]; ~i; i = e[i].next) {
int v = e[i].to;
if (e[i].cap && vis[v] != tim) res = min(res, dis[v] + e[i].cost - dis[x]);
}
}
if (res == INF) return 0;
for (int i = 0; i <= N; i++) if (vis[i] == tim) dis[i] += res;
return 1;
}
int dfs(int x, int f) {
vis[x] = tim;
if (x == T) return f;
int res = 0;
for (int i = fir[x]; ~i; i = e[i].next) {
int v = e[i].to, w = e[i].cost;
if (e[i].cap && dis[x] == dis[v] + w && vis[v] != tim) {
int d = dfs(v, min(f, e[i].cap));
res += d, f -= d;
e[i].cap -= d, e[i ^ 1].cap += d;
if (!f) break;
}
}
return res;
}
void zkw() {
spfa();
int flow = 0, res = 0;
do {
int f = 0;
do {
++tim;
f = dfs(S, INF);
flow += f, res += dis[S] * f;
} while (f);
} while (relabel());
printf("%d %d
", flow, res);
}
int main () {
#ifndef ONLINE_JUDGE
freopen("cpp.in", "r", stdin);
#endif
clearGraph();
scanf("%d %d %d %d", &N, &M, &S, &T);
for (int i = 1; i <= M; i++) {
int u, v, w, f; scanf("%d %d %d %d", &u, &v, &w, &f);
Add_Edge(u, v, w, f);
}
zkw();
return 0;
}