题解 P3381 【【模板】最小费用最大流】

感觉好亏。。 最大流学了Dinic结果费用流用不了Dinic。。。 于是又看了EK（垃圾EK） EK是通过Bfs，找到最短的可行流，并且把整个路径都记录下来，答案加上这个可行流的流量，然后从t倒回去走到s，在过程中把容量进行处理，减去流量。和Dinic也差不到那里去。 然后，费用流的EK，只用把Bfs改成Spfa就可以了，无非是dep数组变成了dis，略有变化而已 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m,s,t,cnt=-1; int head[100100],nxt[100100],to[100100],val[100100],w[100100]; int del[100100],q[100100],dis[100100],f[100100],pre[100100]; void addedge(int x,int y,int z,int k) { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; w[cnt]=z; val[cnt]=k; } bool spfa() { memset(f,0,sizeof(f)); memset(dis,-1,sizeof(dis)); q[1]=s,dis[s]=0,f[s]=1,del[s]=0x7fffffff; int l=0,r=1; while(l<r) { int u=q[++l]; for(int i=head[u];i!=-1;i=nxt[i]) { int v=to[i]; if((dis[v]>dis[u]+val[i] || dis[v]==-1) && w[i]) { dis[v]=dis[u]+val[i]; del[v]=min(del[u],w[i]),pre[v]=i;//记录路径和流量 if(!f[v]) { f[v]=1; q[++r]=v; } } } f[u]=0; } return dis[t]!=-1; } int main() { memset(head,-1,sizeof(head)); scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=m;i++) { int x,y,z,k; scanf("%d%d%d%d",&x,&y,&z,&k); addedge(x,y,z,k); addedge(y,x,0,-k); } int ans=0,res=0; while(spfa()) { ans+=del[t]; res+=dis[t]*del[t];//费用是流量*花费 int tmp=t; while(tmp!=s)//从t倒回去 { w[pre[tmp]]-=del[t]; w[pre[tmp]^1]+=del[t];//处理容量 tmp=to[pre[tmp]^1]; } } printf("%d %d",ans,res); return 0; } ```