模板题：https://www.luogu.org/problemnew/show/P3381
#include<cstdio> #include<queue> #include<cstring> #define rep(i,n) for(register int i=1;i<=n;i++) #define REP(i,a,b) for(register int i=a;i<=b;i++) using namespace std; const int N=5005; const int M=50005; const int INF=(~0u>>1); inline int read() { int s=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=0;c=getchar();} while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();} return f?s:-s; } struct edge { int to,nxt,w,c; edge(int to=0,int nxt=0,int w=0,int c=0):to(to),nxt(nxt),w(w),c(c){} }edges[M<<1]; int n,m,s,t,cnt,ans,maxflow; int head[M<<1],vis[N],d[N],pre[N],infc[N]; queue<int>q; inline void addEdge(int u,int v,int w,int c) { edges[++cnt]=edge(v,head[u],w,c);head[u]=cnt; edges[++cnt]=edge(u,head[v],0,-c);head[v]=cnt; } #define cur edges[i].to inline bool spfa() { memset(vis,0,sizeof vis);rep(i,n)d[i]=INF; infc[s]=INF;d[s]=0;q.push(s);vis[s]=1; while(!q.empty()) { int k=q.front();q.pop();vis[k]=0; for(register int i=head[k];i;i=edges[i].nxt)if(edges[i].w&&d[cur]>d[k]+edges[i].c) { d[cur]=d[k]+edges[i].c; pre[cur]=i;infc[cur]=min(infc[k],edges[i].w); if(!vis[cur]) { vis[cur]=1; q.push(cur); } } } if(d[t]==INF)return 0; return 1; } #undef cur inline void updata() { int tmp=t; while(tmp!=s) { int i=pre[tmp]; edges[i].w-=infc[t]; edges[i^1].w+=infc[t]; tmp=edges[i^1].to; } maxflow+=infc[t]; ans+=d[t]*infc[t]; } int main() { cnt=1;n=read();m=read();s=read();t=read(); rep(i,m) { int u,v,w,c;u=read();v=read();w=read();c=read(); addEdge(u,v,w,c); } while(spfa())updata(); printf("%d %d",maxflow,ans); return 0; }