摘自大神：
https://blog.csdn.net/jzq233jzq/article/details/73123089
源点和汇点，每条边已知其最大流量和单位流量费用，求出其网络最大流和在最大流情况下的最小费用。
每行包含四个正整数ui、vi、wi、fi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi），单位流量的费用为fi。
Edmond-Karp经过修改
很像dinic
正着走spfa（SLF优化）
上代码：
int n, m, s, t;
struct edge
{
int to, w, nx, cost;
} e[N << 1];
int fi[N];
int ce = 1;
int dis[N];
bool vis[N];
int cur[N];
int ans = 0;
inline void add(int u, int v, int w, int c)
{
e[++ce] = edge{v, w, fi[u], c};
fi[u] = ce;
}
int spfa()
{
me(vis, 0);
me(dis, 0x3f);
deque<int> q;
q.push_back(s);
vis[s] = 1;
dis[s] = 0;
while (!q.empty())
{
int u = q.front();
q.pop_front();
for (int i = fi[u]; ~i; i = e[i].nx)
{
int v = e[i].to;
if (e[i].w && dis[u] + e[i].cost < dis[v])
{
dis[v] = dis[u] + e[i].cost;
if (!vis[v])
{
vis[v] = 1;
if (!q.empty() && dis[v] < dis[q.front()])
q.push_front(v);
else
q.push_back(v);
}
}
}
vis[u] = 0;
}
return dis[t] < inf;
}
int dfs(int u, int flow)
{
if (u == t)
{
vis[u] = 1;
return flow;
}
int used = 0;
vis[u] = 1;
for (int &i = cur[u]; ~i; i = e[i].nx)
{
int v = e[i].to;
if ((!vis[v]||v==t) && e[i].w && dis[u] + e[i].cost == dis[v])
{
int di = dfs(v, min(e[i].w, flow - used));
if (di)
e[i].w -= di, e[i ^ 1].w += di, ans += e[i].cost * di, used += di;
if (used == flow)
break;
}
}
return used;
}
int costflow(int s, int t)
{
int res = 0;
while (spfa())
{
vis[t] = 1;
For(i, 1, n) cur[i] = fi[i];
while (vis[t])
{
me(vis, 0);
res += dfs(s, inf);
}
}
return res;
}
int main()
{
#ifndef ONLINE_JUDGE
file("test");
#endif
me(fi, -1);
sdf(n), sdf(m), sdf(s), sdf(t);
while (m--)
{
int u, v, w, c;
sdf(u), sdf(v), sdf(w), sdf(c);
add(u, v, w, c), add(v, u, 0, -c);
}
int res = costflow(s, t);
printf("%d %d", res, ans);
return 0;
}