LibreOJ #6013. 「网络流 24 题」负载平衡最小费用最大流供应平衡问题

2021-10-09 09:51:14

#6013. 「网络流 24 题」负载平衡

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

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

上传者：匿名

提交提交记录统计讨论测试数据

题目描述

G 公司有 n nn 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 n nn 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。

输入格式

文件的第 1 11 行中有 1 11 个正整数 n nn，表示有 n nn 个仓库。
第 2 22 行中有 n nn 个正整数，表示 n nn 个仓库的库存量。

输出格式

输出最少搬运量。

样例

样例输入

5

17 9 14 16 4

样例输出

数据范围与提示

1≤n≤100 1 \leq n \leq 1001≤n≤100

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

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

思路：这是一种供求平衡问题，与「网络流 24 题」餐巾计划是同一种问题。即将一个点拆成2个点来处理，一个需求、一个输出，形成一个二分图。

代码：

#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 c,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.c&&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]].c);

        flow+=d;

        cost+=d*dist[t];

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

        {

            es[pre[i]].c-=d;

            es[pre[i]^].c+=d;

        }

    }

    return cost;

}

ll a[maxn];

int main()

{

    int n;

    scanf("%d",&n);

    int s=,t=*n+;

    ll sum=;

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

    {

        scanf("%lld",&a[i]);

        sum+=a[i];

    }

    ll ave=sum/n;

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

    {

        if(ave<a[i]) addedge(s,i,a[i]-ave,);

        else if(a[i]<ave) addedge(i+n,t,ave-a[i],);

        int l=i-,r=i+;

        if(l<) l=n;

        if(r>n) r=;

        addedge(i,l,inf,),addedge(i,l+n,inf,);

        addedge(i,r,inf,),addedge(i,r+n,inf,);

    }

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

    return ;

}

最小费用最大流供求平衡问题

码农公寓