#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N=5e3+5;
const int M=5e4+5;
const int inf=0x3f3f3f3f3f3f3f3f;
struct Edge{int to,w,next,cost;//w 是容量，cost 是单位流量花费
}edge[M*2];
int head[N],dis[N],vis[N],cur[N];
int n,m,s,t,cnt,min_cost=0;//min_cost 记录最小花费
void add(int u,int v,int w,int cost){edge[cnt]={v,w,head[u],cost};head[u]=cnt++;
}
bool spfa(){memset(vis,0,sizeof vis);memset(dis,inf,sizeof dis);queue<int> q;dis[s]=0;vis[s]=1;q.push(s);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(edge[i].w && dis[u]+edge[i].cost<dis[v]){dis[v]=dis[u]+edge[i].cost;if(!vis[v]) vis[v]=1,q.push(v);}}}//在开始 dfs 之前 vis 已经被初始化成 0 了 if(dis[t]!=inf) return true;return false;
}
int dfs(int u,int flow){vis[u]=1;//标记走过的点，防止死循环 if(u==t) return flow;for(int i=cur[u];i!=-1;i=edge[i].next){cur[u]=i;//当前弧优化 int v=edge[i].to;if(edge[i].w && dis[v]==dis[u]+edge[i].cost && !vis[v]){//dis[v]==dis[u]+edge[i].cost 跟着最短路走 int tmp=dfs(v,min(flow,edge[i].w));if(tmp){edge[i].w-=tmp;edge[i^1].w+=tmp;min_cost+=tmp*edge[i].cost;//累加最小花费 return tmp;}}}vis[u]=0;return 0;
}
int dinic(){int ans=0;while(spfa()){//最短路分层 memcpy(cur,head,sizeof head);// cur 初始化 while(int tot=dfs(s,inf)) ans+=tot;//dfs(s,inf)为 0 时，就说明此时没有增广流 }return ans;
}
signed main(){IOScin >> n >> m >> s >> t;memset(head,-1,sizeof head);for(int i=1;i<=m;i++){int u,v,w,cost;cin >> u >> v >> w >> cost;add(u,v,w,cost);add(v,u,0,-cost);}int flow=dinic();cout << flow << " " << min_cost << endl;return 0;
}
模板题：P3381 【模板】最小费用最大流 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
