洛谷P4015 运输问题(费用流)

题目描述

WW 公司有 mm 个仓库和 nn 个零售商店。第 ii 个仓库有 a_iai​ 个单位的货物;第 jj 个零售商店需要 b_jbj​ 个单位的货物。

货物供需平衡,即\sum\limits_{i=1}^{m}a_i=\sum\limits_{j=1}^{n}b_ji=1∑m​ai​=j=1∑n​bj​ 。

从第 ii 个仓库运送每单位货物到第 jj 个零售商店的费用为 c_{ij}cij​ ​​ 。

试设计一个将仓库中所有货物运送到零售商店的运输方案,使总运输费用最少。

输入输出格式

输入格式:

第 11 行有 22 个正整数 mm 和 nn ,分别表示仓库数和零售商店数。

接下来的一行中有 mm 个正整数 a_iai​ ,表示第 ii 个仓库有 a_iai​ 个单位的货物。

再接下来的一行中有 nn 个正整数 b_jbj​ ,表示第 jj 个零售商店需要 b_jbj​ 个单位的货物。

接下来的 mm 行,每行有 nn 个整数,表示从第 ii 个仓库运送每单位货物到第 jj 个零售商店的费用 c_{ij}cij​ 。

输出格式:

两行分别输出最小运输费用和最大运输费用。

输入输出样例

输入样例#1

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

输出样例#1:

48500
69140

说明

1 \leq n, m \leq 1001≤n,m≤100

挺裸的一道费用流

从S向仓库连容量为a,费用为0的边

从商店向T连容量为b,费用为0的边

从仓库向商店连容量为INF,费用为c的边

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define AddEdge(x,y,z,f) add_edge(x,y,z,f),add_edge(y,x,-z,0)
using namespace std;
const int INF=1e8+10;
const int MAXN=1e4+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int N,M,S,T;
int ansflow,anscost;
int A[MAXN],B[MAXN],C[1001][1001];
struct node
{
    int u,v,w,f,nxt;
}edge[MAXN];
int head[MAXN],num=2;
inline void add_edge(int x,int y,int z,int f)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].w=z;
    edge[num].f=f;
    edge[num].nxt=head[x];
    head[x]=num++;
}
int dis[MAXN],vis[MAXN],Pre[MAXN];
int SPFA()
{
    queue<int>q;
    q.push(S);
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[S]=0;
    while(q.size()!=0)
    {
        int p=q.front();q.pop();
        vis[p]=0;
        for(int i=head[p];i!=-1;i=edge[i].nxt)
        {
            if(edge[i].f>0&&dis[edge[i].v]>dis[p]+edge[i].w)
            {
                dis[edge[i].v]=dis[p]+edge[i].w;
                Pre[edge[i].v]=i;
                if(!vis[edge[i].v])
                    q.push(edge[i].v),vis[edge[i].v]=1;
            }
        }
    }
    return dis[T]<=INF;
}
int F()
{
    int nowflow=INF;
    for(int now=T;now!=S;now=edge[Pre[now]].u)
        nowflow=min(nowflow,edge[Pre[now]].f);
    for(int now=T;now!=S;now=edge[Pre[now]].u)
        edge[Pre[now]].f-=nowflow,
        edge[Pre[now]^1].f+=nowflow;
    anscost+=nowflow*dis[T];
}
void MCMF()
{
    while(SPFA()) F();
    printf("%d\n",abs(anscost));
    anscost=0;
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #endif
    memset(head,-1,sizeof(head));
    N=read(),M=read();
    S=N+M+1;T=N+M+2;
    for(int i=1;i<=N;i++)
        A[i]=read();
    for(int i=1;i<=M;i++)
        B[i]=read();
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            C[i][j]=read();
            
    for(int i=1;i<=N;i++)
        AddEdge(S,i,0,A[i]);
        
    for(int i=1;i<=M;i++)    
        AddEdge(i+N,T,0,B[i]);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            AddEdge(i,j+N,C[i][j],INF);
    MCMF();
    memset(head,-1,sizeof(head));
    num=2;
    for(int i=1;i<=N;i++)
        AddEdge(S,i,0,A[i]);
    for(int i=1;i<=M;i++)    
        AddEdge(i+N,T,0,B[i]);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            AddEdge(i,j+N,-C[i][j],INF);
    MCMF();
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏域名资讯

2位数字域名竟千万 交易动态一起看

2数字域名80.com完成交易了,价格高达千万元人民币!让我们一起看下本周域名交易动态吧!

93300
来自专栏数据小魔方

财经小知识——CRS风暴与全球离岸金融中心

2017年元旦,中国政府开始正式启动CRS,听起来好高端哦,但是管我屁事! 先别着急,如果你有大量的资产或者收入配置在海外,这个真的就关你的事儿了,那么具体CR...

29970
来自专栏美团技术团队

【美团技术团队博客】RACSignal的Subscription深入分析

ReactiveCocoa是一个FRP的思想在Objective-C中的实现框架,目前在美团的项目中被广泛使用。对于ReactiveCocoa的基本用法,网上有...

46140
来自专栏域名资讯

蚂蜂窝D轮融资1.33亿美元,域名保护到位

三拼域名虽然字符较长,但对于国内用户来说不难记忆。目前不少终端启用三拼域名,例如人人车(renrenche.com)、聚美丽(jumeili.cn...

21000
来自专栏Python小屋

Python计算合理避税后收入增加情况

假设张三所在团队有一小笔收入,但是超出800元以上的部分要交20%的税,为了提高总收入,可以申报多人合作完成,这样的话每人800之内的部分都不需要扣税,那么总收...

32150
来自专栏域名资讯

高手一出手 9枚域名获利百万元以上!

在米市,想必大家对Mike mann并不陌生,Mike mann是海外的域名投资人,在国内也有很多米友们听过他的名号,他在域名投资上的收益更是让人赞...

30400
来自专栏镁客网

四川规定除了买无人机需要实名之外,还要考取无人机“驾照”

16400
来自专栏王磊的博客

Express调用mssql驱动公共类dbHelper

直接上代码: /** * Created by chaozhou on 2015/9/18. */ var mssql = require('mssql')...

41470
来自专栏大数据文摘

陆金所融资12亿美元的PPT长什么样?

458120
来自专栏FSociety

pyecharts实现星巴克门店分布可视化分析

该数据集来源Kaggle,囊括了截至2017/2月份全球星巴克门店的基础信息,其中包括品牌名称、门牌地址、所在国家、经纬度等一系列详细的信息。

47520

扫码关注云+社区

领取腾讯云代金券