//EK 最小费用最大流 //只需将最大流中的bfs改为SPFA即可
//注意 若要跑最大费用最大流 只需在加边时将正反边费用分别取反
//跑完最小费用最大流后把mincost取反即可 #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<queue> #define ll long long #define ull unsigned long long #define INF 0x3f3f3f3f using namespace std; int n,m,s,t,maxflow,mincost,cnt=-1; int head[5001],pre[5001],mflow[5001],mcost[5001],vis[5001]; //pre最短路上每个点所连的前一条边 mflow源点到每个点的最大增量 mcost源点到每个点的最小费用 vis为SPFA数组 struct uio{ int to,nxt,flow,cost; }edge[100001]; void add(int x,int y,int f,int c) { edge[++cnt].nxt=head[x]; edge[cnt].to=y; edge[cnt].flow=f; edge[cnt].cost=c; head[x]=cnt; } bool spfa() { memset(mflow,0x3f,sizeof(mflow)); memset(mcost,0x3f,sizeof(mcost)); memset(vis,0,sizeof(vis)); queue<int> que; que.push(s); mcost[s]=0; pre[t]=-1; vis[s]=1; while(!que.empty()) { int now=que.front(); que.pop(); vis[now]=0; for(int i=head[now];i!=-1;i=edge[i].nxt) { int y=edge[i].to; if(edge[i].flow>0&&mcost[y]>mcost[now]+edge[i].cost)//是正边 { mcost[y]=mcost[now]+edge[i].cost; pre[y]=i; mflow[y]=min(mflow[now],edge[i].flow); if(!vis[y]) { vis[y]=1; que.push(y); } } } } return pre[t]!=-1;//若能增广到汇点 则其前一条边就会有标记 } void EK() { while(spfa()) { int now=t; maxflow+=mflow[t]; mincost+=mcost[t]*mflow[t]; while(now!=s)//一直回溯到源点 { edge[pre[now]].flow-=mflow[t]; edge[pre[now]^1].flow+=mflow[t]; now=edge[pre[now]^1].to; } } } int main() { memset(head,-1,sizeof(head)); scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=m;i++) { int u,v,w,p; scanf("%d%d%d%d",&u,&v,&w,&p); add(u,v,w,p); add(v,u,0,-p); } EK(); printf("%d %d ",maxflow,mincost); return 0; }