#includeusing namespace std; const int MM=100005; int u,v,w,c,tmp,n,m,s,t,tot=1,flow,cost,nxt[MM],to[MM],fl[MM],cs[MM],dis[MM],head[MM],vis[MM],pre[MM],in[MM]; void add(int u,int v,int w,int c) { nxt[++tot]=head[u]; to[tot]=v; fl[tot]=w; cs[tot]=c; head[u]=tot; } bool spfa() { queue<int> q; memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); q.push(s); dis[s]=0; in[s]=1<<30; while(!q.empty()) { int now=q.front(); vis[now]=0; q.pop(); for(int i=head[now];i;i=nxt[i]) { if(!fl[i])continue; if(dis[now]+cs[i]<dis[to[i]]) { dis[to[i]]=dis[now]+cs[i]; in[to[i]]=min(in[now],fl[i]); pre[to[i]]=i; if(!vis[to[i]]) { vis[to[i]]=1; q.push(to[i]); } } } } if(dis[t]==1061109567) return 0; return 1; } void cf() { while(spfa()) { flow+=in[t]; cost+=dis[t]*in[t]; tmp=t; while(tmp!=s) { fl[pre[tmp]]-=in[t]; fl[pre[tmp]^1]+=in[t]; tmp=to[pre[tmp]^1]; } } } int main() { cin>>n>>m>>s>>t; for(int i=1;i) { cin>>u>>v>>w>>c; add(u,v,w,c); add(v,u,0,-c); } cf(); cout< ' '<<cost; return 0; }
Original: https://www.cnblogs.com/29taorz/p/15727637.html
Author: T_X蒻
Title: 费用流 板子
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/644071/
转载文章受原作者版权保护。转载请注明原作者出处！