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

朴素的EK+SPFA ```cpp #include<bits/stdc++.h> #define MAXN 5100 #define MAXM 100100 #define INF 1073741824 using namespace std;//INF不要开太大了否则可能会在一些操作下越界 struct Edge{ int from,to,re,c;//不记录流量和容量而直接记录残量可以节约空间方便操作（re=res,c=cost） Edge(int _from,int _to,int _re,int _c) {from=_from,to=_to,re=_re,c=_c;} Edge(){} }; Edge table[MAXM+1];//一定要记得给逆向边开数组（因为这个为P3381贡献了N个TLE+RE） int pre[MAXN+1],dis[MAXN+1];//前驱&&最短路（权值为cost） int nxt[MAXM+1],fr[MAXM+1];//记录邻接表 int n,m,s,t,tot=1; int max_f,min_c;//最大流最小费用 bool inq[MAXN+1]; deque<int> mession;//双向队列 void MCMF(){ while(true){ fill(dis+1,dis+n+1,INF); memset(inq,false,sizeof(inq)); dis[s]=0; mession.push_back(s); inq[s]=true,dis[s]=0; int now;//现在点 while(!mession.empty()){ now=mession.front(),mession.pop_front(); inq[now]=false; for(int i=fr[now];i!=-1;i=nxt[i]){ Edge &tar=table[i];//目标点 if(tar.re>0&&dis[tar.to]>dis[now]+tar.c){ dis[tar.to]=dis[now]+tar.c; pre[tar.to]=i; if(!inq[tar.to]){ if(mession.empty()||dis[tar.to]<dis[mession.front()]) mession.push_front(tar.to);//优先处理的优化（要加入空队列的判断，否则会RE） else mession.push_back(tar.to); inq[tar.to]=true;//是否在队列中 } } } } if(dis[t]==INF) return;//集中的EK写法（只有一个函数）（此时不可增广） int ret=INF; for(int i=t;i!=s;i=table[pre[i]].from) if(ret>table[pre[i]].re) ret=table[pre[i]].re;//获取最小的可增广流量 for(int i=t;i!=s;i=table[pre[i]].from) table[pre[i]].re-=ret,table[pre[i]^1].re+=ret;//增广 max_f+=ret,min_c+=ret*dis[t]; } } inline int read(){//不用考虑负数的读入优化 int num=0; char c; while(isspace(c=getchar())); while((num=num*10+c-48)&&isdigit(c=getchar())); return num; } int main(){ n=read(),m=read(),s=read(),t=read(); memset(nxt,-1,sizeof(nxt));//注意结束的标记 for(int i=1;i<=m;i++){ int x=read(),y=read(),c1=read(),c2=read(); table[++tot]=Edge(x,y,c1,c2); nxt[tot]=fr[x],fr[x]=tot; table[++tot]=Edge(y,x,0,-c2);//方便直接调用正向边逆向边 nxt[tot]=fr[y],fr[y]=tot; } MCMF(); printf("%d %d",max_f,min_c); return 0; } ```