脚本宝典收集整理的这篇文章主要介绍了费用流，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

费用流：

定义：

给定一个网络 (G=(V,E)), 每条边除了有容量限制 (c(u,v)) , 还有一个单位流量的费用 (w(u,v))

当 ((u,v)) 的流量 (f(u,v)) 时，需要花费 (f(u,v) times w(u,x))

(w) 也满足对称性，即 (w(u,v)+w(v,u)=0)

则该网络中总花费最小的最大流称为 最小费用最大流。

即在最大化 (sum_{(s,v)in E}f(s,v)) 的前提下最小化 (sum_{(u,v)in E} f(u,v) times w(u,v))

分析:

可以使用 (SSP) 算法。

(SSP) 算法是一个贪心的算法，它的思路是每次寻找单位费用最小的增广路进行增广，直到图上不存在增广路为止。

如果图上存在单位费用为负的圈， (SSP) 算法无法算出，需要用消圈算法消去负环。

使用：

只需要将 (EK) 算法或 (Dinic) 算法中寻找增广路的过程，替换为用最短路算法寻找单位费用最小的增广路即可。

@R_283_1304@为 (O(nmk)) ，即为 (SPFA times) 增广路的长度

代码：

#include<bITs/stdc++.h>
using namespace std;
#define ll long long 
const int inf=0x3f3f3f3f,N=5005,M=200005;
int nxt[M],ver[M],tot=1,Edge[M],head[N],w[M];
int n,m,s,t;
int maxflow,mincost;
int dis[N],PRe[N],cur[N],last[N],flow[N];
bool vis[N];
queue<int> q;

void add(int x,int y,int z,int f){
    ver[++tot]=y; edge[tot]=z; nxt[tot]=head[x]; head[x]=tot; w[tot]=f;
    ver[++tot]=x; edge[tot]=0; nxt[tot]=head[y]; head[y]=tot; w[tot]=-f;
}

bool spfa(int s,int t){
    memset(dis,0x7f,sizeof(dis));
    memset(flow,0x7f,sizeof(flow));
    memset(vis,0,sizeof(vis));
    q.push(s); vis[s]=1; dis[s]=0; pre[t]=-1;
    while(!q.empty()){
        int x=q.front(); q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i],z=edge[i],W=w[i];
            if(!z||dis[y]<=dis[x]+W) continue;//最短路算法
            dis[y]=dis[x]+W;
            pre[y]=x;//记录上一个点
            last[y]=i;//记录上一条边
            flow[y]=min(flow[x],z);
            if(!vis[y]){vis[y]=1; q.push(y);}
        }
    }
    return pre[t]!=-1;
}

void MCMF(){
    while(spfa(s,t)){
        int x=t;
        maxflow+=flow[x]; mincost+=flow[x]*dis[x];
        while(x!=s){
            edge[last[x]]-=flow[t];
            edge[last[x]^1]+=flow[t];
            x=pre[x];
        } 
    }
}

int main(){
    cin>>n>>;m>>s>>t;
    for(int i=1,x,y,z,f;i<=m;i++){
        scanf("%d%d%d%d",&amp;x,&y,&z,&f); add(x,y,z,f); 
    }
    MCMF();
    cout<<maxflow<<" "<<mincost<<endl;
    System("pause");
    return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的费用流全部内容，希望文章能够帮你解决费用流所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。