网络流 费用流 EK算法

模板题：洛谷p3381

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10,M=5e4+10,INF=0x3f3f3f3f;
typedef long long LL;
int n,m,s,t,id=1;
int e[M<<1],h[N],cap[M<<1],d[M<<1],ne[M<<1];
int dp[N],vis[N],mf[N],pre[N];
void add(int u,int v,int w,int c){id++;e[id]=v;cap[id]=w;d[id]=c;ne[id]=h[u];h[u]=id;
}bool spfa(){memset(dp,0x3f,sizeof(dp));memset(mf,0,sizeof(mf));queue<int> q;q.push(s);vis[s]=1;dp[s]=0;mf[s]=INF;while(q.size()){int u=q.front();q.pop();vis[u]=0;for(int i=h[u];i;i=ne[i]){int v=e[i],w=d[i],c=cap[i];if(dp[v]>dp[u]+w&&c){dp[v]=dp[u]+w;mf[v]=min(mf[u],c);pre[v]=i;if(!vis[v]){q.push(v);vis[v]=1;}}}}return mf[t]>0;
}void EK(){LL flow=0,cost=0;while(spfa()){for(int v=t;v!=s;){int i=pre[v];cap[i]-=mf[t];cap[i^1]+=mf[t];v=e[i^1];}flow+=mf[t];cost+=mf[t]*dp[t];}cout<<flow<<' '<<cost<<endl;
}int main(){cin.tie(nullptr)->sync_with_stdio(false);cin>>n>>m>>s>>t;for(int i=1;i<=m;i++){int u,v,w,c;cin>>u>>v>>w>>c;add(u,v,w,c);add(v,u,0,-c);}EK();return 0;
}