网络流——最小费用最大流-白红宇

网络流——最小费用最大流

阅读量：6848 次

发布时间：2019-06-26

本文共 1840 字，大约阅读时间需要 6 分钟。

前言

Q：为什么突然想搞网络流？

A：迫于~~Tham_蛤mu~~的淫威

算法过程

用最短路算法求出s->t的路径(把路径要抠出来,而且每条边要有容量)

算一下路径里面的可以流过的最大的流量

发现此时的花费就是$dis_t*Flow$,累加即可.

重复1->3直到不能够到达t.

代码实现

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             using namespace std;#define ll long long#define re register#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)inline int gi(){ int f=1,sum=0;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum;}const int N=5010,M=50010,Inf=1e9+10;int n,m,s,t,MaxFlow,MinCost;class Graph{private: int front[N],cnt,nxt[M<<1],to[M<<1],w[M<<1],c[M<<1],dis[N],vis[N],fa[N],from[N]; bool SPFA(){ queue
             
              Q;while(!Q.empty())Q.pop(); Q.push(s);memset(dis,127,sizeof(dis));vis[s]=1;dis[s]=0; while(!Q.empty()){ int u=Q.front();Q.pop();vis[u]=0; for(int i=front[u];i!=-1;i=nxt[i]){ int v=to[i]; if(w[i] && dis[v]>dis[u]+c[i]){ dis[v]=dis[u]+c[i];from[v]=i;fa[v]=u; if(!vis[v]){ vis[v]=1;Q.push(v); } } } } return dis[0]!=dis[t]; }public: void Add(int u,int v,int val,int f){to[cnt]=v;nxt[cnt]=front[u];front[u]=cnt;w[cnt]=val;c[cnt]=f;++cnt;} void init(){memset(front,-1,sizeof(front));cnt=0;} void Solve(){ while(SPFA()){ int d=Inf; for(int i=t;i!=s;i=fa[i])d=min(d,w[from[i]]); MaxFlow+=d;MinCost+=d*dis[t]; for(int i=t;i!=s;i=fa[i]){w[from[i]]-=d;w[from[i]^1]+=d;} } }}MfMc;int main(){ n=gi();m=gi();s=gi();t=gi(); MfMc.init(); for(int i=1;i<=m;i++){ int u=gi(),v=gi(),val=gi(),f=gi(); MfMc.Add(u,v,val,f);MfMc.Add(v,u,0,-f); } MfMc.Solve(); printf("%d %d\n",MaxFlow,MinCost); return 0;}