前置知识：
简要题意：
给定网络图，求图的最大流，以及流量为最大流时的最小费用。
现在假设你们看了那篇网络流博客之后，所有人都会了 ( ext{EK , FF , dinic}) 算法。
然后我们来介绍一个新的思想。
假设我们从最短路的角度出发，仍然采用之前那个 “反悔” 思想，那么此时 可以用 ( ext{SPFA}) 来实现每次增广，增广的时候，你会发现原来代码里的 found 函数用来查询反向边。但是这次我们不用了，我们再建边 (u
ightarrow v) 的时候，就建立一个 ( ext{rev})，表示当前边在另外一个顶点里的编号。
比方说 $3 ightarrow 5$ 在 $3$ 的边中是第 $2$ 条，那么 $5$ 对于这条边的 ( ext{rev}=2)，便于我们迅速查找反向边。
然后考虑如何在最大流的基础上求出最小费用？我们沿袭 ( ext{SPFA}) 中的 ( ext{dis})，这是用来求最短路的，那么我们正好用 ( ext{dis}) 把费用（即最短路中的边权）记录一下，正好可以达到这个效果。
所以说 ( ext{SPFA}) 在某种意义上并没有死，因为它的常数出奇地小或许能卡过一些题目（比方说这道）。
当然了，如果真想用 ( ext{dijkstra}) ，那么要用到 Johnson 全源最短路 中 ( ext{Johnson}) 提出的，“构造上帝节点，依据最短路将边权构造为非负” 的思想。那样的话复杂度就是 (O(nm log n)) 了。
时间复杂度：(O(n^2m)).（显然 ( ext{SPFA}) 一次是 (n^2) 的）
实际得分：$100pts$.（因为实际上根本跑不满的，不可能每次都会到上限）
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+1;
inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
struct node {
int to,flow,rev,cost; //to 是边终点 , flow 是流量 , rev 是反向边编号 , cost 是费用
} ;
vector<node> G[N];
int dis[N],pre1[N],pre2[N]; //pre1[i] 是正常网络流的前驱 pre2[i] 是前驱的边编号 , 类似于 rev , 有利于最后的反悔操作
int flow[N],n,m,s,t,ans;
bool vis[N]; int maxf;
inline bool SPFA() {
fill(dis+1,dis+1+n,2e9);
memset(vis,0,sizeof(vis));
queue<int> q; dis[s]=0; vis[s]=1; flow[s]=2e9;
q.push(s);
while(!q.empty()) {
int u=q.front(); q.pop(); vis[u]=0;
// printf("%d
",u);
for(int i=0;i<G[u].size();i++) {
node t=G[u][i]; int v=t.to; //向外增广
if(t.flow>0 && t.cost+dis[u]<dis[v]) {
dis[v]=dis[u]+t.cost;
pre1[v]=u; pre2[v]=i;
flow[v]=min(flow[u],t.flow); //记录答案
if(!vis[v]) vis[v]=1,q.push(v);
}
}
}
// for(int i=1;i<=n;i++) printf("%d ",dis[i]); puts("");
// for(int i=1;i<=n;i++) printf("%d ",flow[i]); puts("");
// for(int i=1;i<=n;i++) printf("%d ",pre1[i]); puts("");
// for(int i=1;i<=n;i++) printf("%d ",pre2[i]); puts("");
return dis[t]!=(2e9);
}
inline void update() {
int k=t; while(k-s){ //不到源点就继续反悔
int p=pre1[k],q=pre2[k];
G[p][q].flow-=flow[t];
G[k][G[p][q].rev].flow+=flow[t]; //套路
k=p;
} maxf+=flow[t];
ans+=dis[t]*flow[t]; //费用更新
}
inline void dinic() {
while(SPFA()) update();
}
int main(){
n=read(),m=read(),s=read(),t=read();
while(m--) {
int u=read(),v=read(),w=read(),f=read();
G[u].push_back(node{v,w,G[v].size(),f});
G[v].push_back(node{u,0,G[u].size()-1,-f});
} dinic();
printf("%d %d
",maxf,ans);
return 0;
}