LIbreOJ #6011. 「网络流 24 题」运输问题最小费用最大流

2022-03-22 10:28:39

#6011. 「网络流 24 题」运输问题

内存限制：256 MiB时间限制：1000 ms标准输入输出

题目类型：传统评测方式：文本比较

上传者：匿名

题目描述

W 公司有 m mm 个仓库和 n nn 个零售商店。第 i ii 个仓库有 ai a_iai 个单位的货物；第 j jj 个零售商店需要 bj b_jbj 个单位的货物。货物供需平衡，即 ∑i=1mai=∑j=1nbj \sum\limits_{i = 1} ^ m a_i = \sum\limits_{j = 1} ^ n b_ji=1∑mai=j=1∑nbj。从第 i ii 个仓库运送每单位货物到第 j jj 个零售商店的费用为 cij c_{ij}cij。试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。

输入格式

第 1 11 行有 2 22 个正整数 m mm 和 n nn，分别表示仓库数和零售商店数。接下来的一行中有 m mm 个正整数 ai a_iai，表示第 i ii 个仓库有 ai a_iai 个单位的货物。再接下来的一行中有 n nn 个正整数 bj b_jbj，表示第 j jj 个零售商店需要 bj b_jbj 个单位的货物。接下来的 m mm 行，每行有 n nn 个整数，表示从第 i ii 个仓库运送每单位货物到第 j jj 个零售商店的费用 cij c_{ij}cij。

输出格式

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

样例

样例输入

2 3

220 280

170 120 210

77 39 105

150 186 122

样例输出

48500

69140

数据范围与提示

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

题目链接：https://loj.ac/problem/6011

题意：中文题意，意思明显。

思路：最小费用最大流版子题。先跑一发最小费用最大流，然后费用取法，再跑一发最小费用最大流，答案取法就是最大费用最大流。

代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<vector>

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

#define PI acos(-1.0)

const int maxn=1e3+,maxm=1e5+,inf=0x3f3f3f3f,mod=1e9+;

const ll INF=1e13+;

struct edge

{

    int from,to;

    ll cap,flow;

    ll w;

};

vector<edge>es;

vector<int>G[maxn];

int pre[maxn];

ll dist[maxn];

inline void addedge(int u,int v,ll c,ll w)

{

    es.push_back((edge)

    {

        u,v,c,,w

    });

    es.push_back((edge)

    {

        v,u,,,-w

    });

    int x=es.size();

    G[u].push_back(x-);

    G[v].push_back(x-);

}

bool spfa(int s,int t)

{

    static std::queue<int> q;

    static bool inq[maxn];

    memset(dist,INF,sizeof(ll)*maxn);

    memset(inq,false,sizeof(bool)*maxn);

    pre[s]=-;

    dist[s]=;

    q.push(s);

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        inq[u]=false;

        for(int i=; i<G[u].size(); i++)

        {

            edge e=es[G[u][i]];

            if(e.cap>e.flow&&dist[e.to]>dist[u]+e.w)

            {

                pre[e.to]=G[u][i];

                dist[e.to]=dist[u]+e.w;

                if(!inq[e.to]) q.push(e.to),inq[e.to]=true;

            }

        }

    }

    return dist[t]<inf;

}

ll dinic(int s,int t)

{

    ll flow=,cost=;

    while(spfa(s,t))

    {

        ll d=INF;

        for(int i=t; i!=s; i=es[pre[i]].from)

            d=min(d,es[pre[i]].cap-es[pre[i]].flow);

        flow+=d;

        cost+=d*dist[t];

        for(int i=t; i!=s; i=es[pre[i]].from)

        {

            es[pre[i]].flow+=d;

            es[pre[i]^].flow-=d;

        }

    }

    return cost;

}

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    int s=,t=n+m+;

    for(int i=; i<=n; i++)

    {

        ll a;

        scanf("%lld",&a);

        addedge(s,i,a,0LL);

    }

    for(int i=; i<=m; i++)

    {

        ll b;

        scanf("%lld",&b);

        addedge(i+n,t,b,0LL);

    }

    for(int i=; i<=n; i++)

    {

        for(int j=; j<=m; j++)

        {

            ll c;

            scanf("%lld",&c);

            addedge(i,j+n,INF,c);

        }

    }

    printf("%lld\n",dinic(s,t));

    for(int i=;i<es.size();i++)

        es[i].flow=,es[i].w=-es[i].w;

    printf("%ld\n",-dinic(s,t));

    return ;

}

最小费用最大流

码农公寓