洛谷P4015 运输问题

@Pelom  November 9, 2019

题意

有$m$个仓库和$n$个零售商店。第$i$个仓库有$a_i$个单位的货物;第$j$个零售商店需要$b_j$个单位的货物
从第$i$个仓库运送每单位货物到第$j$个零售商店的费用为$c_{ij}$
试设计一个将仓库中所有货物运送到零售商店的运输方案,使总运输费用最少

数据范围:$1 \le n,m \le 100$

题解

建立超级源点与超级汇点
由超级源点向每个仓库建流量为$a_i$,费用为$0$的边;由每个商店向超级汇点建流量为$b_i$,费用为$0$的边;由仓库向商店建流量为$\text{inf}$,费用为$c_{ij}$的边
然后跑从超级源点到超级汇点的费用流,便可以得到最小运输费用
而求最大运输费用,只需将费用取反后再跑一次费用流

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=5000+10;
const int INF=0x3f3f3f3f;
int m,n,u,v;
int a[N],b[N],c[N][N];
int cnt=1,s,t;
int head[N],lst[N],pre[N],dis[N],w[N];
bool vis[N];
int maxFlw,cst;
struct edge{
    int nxt,to,w,val;
} e[N<<1];
inline void add(int u,int v,int w,int val){
    e[++cnt]=(edge){head[u],v,w,val};
    head[u]=cnt;
}
inline bool SPFA(){
    queue<int> Q;
    memset(dis,0x3f,sizeof(dis));
    memset(w,0x3f,sizeof(w));
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    vis[s]=1;
    pre[t]=-1;
    Q.push(s);
    for(;!Q.empty();){
        int u=Q.front();
        Q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(e[i].w>0 && dis[v]>dis[u]+e[i].val){
                dis[v]=dis[u]+e[i].val;
                pre[v]=u;
                lst[v]=i;
                w[v]=min(w[u],e[i].w);
                if(!vis[v]){
                    vis[v]=1;
                    Q.push(v);
                }
            }
        }
    }
    return pre[t]!=-1;
}
inline void EK(){
    for(;SPFA();){
        int u=t;
        maxFlw+=w[t];
        cst+=w[t]*dis[t];
        for(;u!=s;){
            e[lst[u]].w-=w[t];
            e[lst[u]^1].w+=w[t];
            u=pre[u];
        }
    }
}
int main(){
    scanf("%d%d",&m,&n);
    s=0,t=m+n+1;
    for(int i=1;i<=m;i++){
        scanf("%d",&a[i]);
        add(s,i,a[i],0);
        add(i,s,0,0);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
        add(i+m,t,b[i],0);
        add(t,i+m,0,0);
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++){
            scanf("%d",&c[i][j]);
            add(i,j+m,INF,c[i][j]);
            add(j+m,i,0,-c[i][j]);
        }
    Dinic();
    printf("%d\n",cst);
    cnt=1;
    maxFlw=cst=0;
    memset(head,0,sizeof(head));
    for(int i=1;i<=m;i++){
        add(s,i,a[i],0);
        add(i,s,0,0);
    }
    for(int i=1;i<=n;i++){
        add(i+m,t,b[i],0);
        add(t,i+m,0,0);
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++){
            add(i,j+m,INF,-c[i][j]);
            add(j+m,i,0,c[i][j]);
        }
    EK();
    printf("%d",-cst);
    return 0;
}

添加新评论