网络流24题之十七 运输问题

2 3
220 280
170 120 210
77 39 105
150 186 122

48500
69140

模型

费用流问题。

实现

把所有仓库看做二分图中顶点Xi，所有零售商店看做二分图中顶点Yi，建立附加源S汇T。

1、从S向每个Xi连一条容量为仓库中货物数量ai，费用为0的有向边。
2、从每个Yi向T连一条容量为商店所需货物数量bi，费用为0的有向边。
3、从每个Xi向每个Yj连接一条容量为无穷大，费用为cij的有向边。

求最小费用最大流，最小费用流值就是最少运费，求最大费用最大流，最大费用流值就是最多运费。

分析

把每个仓库想象成一个中转站，由源点运来ai单位货物，运费为0，每个商店也为一个中转站，运向目标汇点bi单位货物。每个仓库和零售商店之间有一条道路，容量为无穷大，费用为单位运费cij。求从源点到汇点的费用流，就是运费。

代码

#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
#include <string>
#include <cstring>
#include <iostream>
#define M 50000
#define N 500
#define INF 0x33333333
#define min(x,y) ((x<y)?(x):(y))
using namespace std;
typedef pair<int,int> Pair;
map <string,int>ma;
struct node{int from,to,next,flow,cost;}e[M];
int tot=-1,st[M];
int n,m,x,y,z;
int pe[N],pv[N],dis[N],vis[N];
void add(int x,int y,int z,int zz){
    e[++tot].to=y;
    e[tot].from=x;
    e[tot].flow=z;
    e[tot].cost=zz;
    e[tot].next=st[x];
    st[x]=tot;
}
void add_edge(int x,int y,int z,int zz){add(x,y,z,zz),add(y,x,0,-zz);}
queue<int>que;
bool spfa(int S,int T)
{
    for (int i=S;i<=T;i++)
        dis[i]=-INF;
    memset(vis,0,sizeof vis);
    que.push(S),vis[S]=1,dis[S]=0;
    while(!que.empty())
    {
        int now=que.front();que.pop();vis[now]=0;
        for (int i=st[now];~i;i=e[i].next)
            if (e[i].flow>0 && dis[e[i].to]<dis[now]+e[i].cost)
            {
                dis[e[i].to]=dis[now]+e[i].cost;
                pe[e[i].to]=i,pv[e[i].to]=now;
                if (!vis[e[i].to])
                    vis[e[i].to]=1,que.push(e[i].to);
            }
    }
    return dis[T]!=-INF;
}
Pair mfmc(int S,int T)
{
    int COST=0,FLOW=0,flow;
    while(spfa(S,T))
    {
        flow=0x3f3f3f3f;
        for (int i=T;i!=S;i=pv[i])
            flow=min(flow,e[pe[i]].flow);
        COST+=flow*dis[T];
        FLOW+=flow;
        for (int i=T;i!=S;i=pv[i])
            e[pe[i]].flow-=flow,e[pe[i]^1].flow+=flow;
    }
    return make_pair(FLOW,COST);
}
bool minspfa(int S,int T)
{
    memset(dis,0x33,sizeof dis);
    memset(vis,0,sizeof vis);
    que.push(S),vis[S]=1,dis[S]=0;
    while(!que.empty())
    {
        int now=que.front();que.pop();vis[now]=0;
        for (int i=st[now];~i;i=e[i].next)
            if (e[i].flow>0 && dis[e[i].to]>dis[now]+e[i].cost)
            {
                dis[e[i].to]=dis[now]+e[i].cost;
                pe[e[i].to]=i,pv[e[i].to]=now;
                if (!vis[e[i].to])
                    vis[e[i].to]=1,que.push(e[i].to);
            }
    }
    return dis[T]<INF;
}
Pair minfmc(int S,int T)
{
    int COST=0,FLOW=0,flow;
    while(minspfa(S,T))
    {
        flow=INF;
        for (int i=T;i!=S;i=pv[i])
            flow=min(flow,e[pe[i]].flow);
        COST+=flow*dis[T];
        FLOW+=flow;
        for (int i=T;i!=S;i=pv[i])
            e[pe[i]].flow-=flow,e[pe[i]^1].flow+=flow;

    return make_pair(FLOW,COST);
}
main()
{
    int m,from,to,a[N],b[N],cost[N][N];
    scanf("%d%d",&m,&n);
    memset(e,-1,sizeof e);
    memset(st,-1,sizeof st);
    int S=0,T=n+m+1;
    for (int i=1;i<=m;i++)
        scanf("%d",&a[i]);
    for (int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
            scanf("%d",&cost[i][j]);
    for (int i=1;i<=m;i++)
        add_edge(S,i,a[i],0);
    for (int i=1;i<=n;i++)
        add_edge(i+m,T,b[i],0);
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
            add_edge(i,j+m,INF,cost[i][j]);
    Pair ans=minfmc(S,T);
    printf("%d\n",ans.second);
    memset(e,-1,sizeof e);
    memset(st,-1,sizeof st);
    for (int i=1;i<=m;i++)
        add_edge(S,i,a[i],0);
    for (int i=1;i<=n;i++)
        add_edge(i+m,T,b[i],0);
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
            add_edge(i,j+m,INF,cost[i][j]);
    ans=mfmc(S,T);
    printf("%d\n",ans.second);
}