P4016 负载平衡问题(网络流24题-费用流)

题目链接

https://www.luogu.org/problem/P4016

题目大意

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

解题思路

最终状态每一个仓库的流量一定是平均数.
所以每一个大于平均数的仓库可以向外送东西,每一个小于平均数的仓库必须要从别的进东西.
每次运输都是有代价的,而代价与运输的多少也有直接关系.
自然就是最小费用最大流了.最大流保证了一定能平衡收支,最小费用保证在收支平衡的情况下花费最少了.
首先先计算出他们的平均数,用每个数都减去平均数得到新的值,这个值如果是负数意味着需要从别的地方搞过一点来,如果正数就说明可以往外送一点.
我们建立超级源点和超级汇点(这套路很常见的)
如果权值为正,即储存量大于平均值,我们就从s向它连一条边,最大流为储存值-平均值,费用为0,图论意义就是它可以从源点免费获得多出来的储存值-平均值的流量,就相当于自身有储存值-平均值的流量,上面不是说了吗,建一个超级源点,就是代替这个功能.
如果权值为负,即储存值小于平均值,我们就从它向t连一条边,最大流量为平均值-储存值,费用为0,图论意义就是它必须从别的节点传来流量,并且汇入自身,意义类比与上面所说.
对于每一个可以互相传的节点,即左邻居和右邻居,需要分别向他们连边,表示自己的流可以流过去.

代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e2;
struct node
{
    int next,len,w,to;
} edge[2*maxn];

int head[maxn],cnt,dis[maxn*2],flow[2*maxn],vis[2*maxn],pre[2*maxn],
    last[2*maxn],a[maxn];
int maxflow,mincost;

void addedge(int u,int v,int len,int w)
{
    edge[cnt].to=v;
    edge[cnt].len=len;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;
    edge[cnt].len=0;
    edge[cnt].w=-w;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}

bool spfa(int s,int t)
{
    memset(dis,0x7f,sizeof(dis));
    memset(flow,0x7f,sizeof(flow));
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(s);
    vis[s]=1;
    dis[s]=0;
    pre[t]=-1;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        vis[now]=0;
        for(int i=head[now]; i!=-1; i=edge[i].next)
        {
            int v = edge[i].to;
            if(edge[i].len>0&&dis[v]>dis[now]+edge[i].w)
            {
                dis[v]=dis[now]+edge[i].w;
                pre[v]=now;
                last[v]=i;
                flow[v]=min(flow[now],edge[i].len);
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(edge[i].to);
                }
            }
        }
    }
    return pre[t]!=-1;
}

void mcmf(int s,int t)
{
    while(spfa(s,t))
    {
        int now=t;
        maxflow+=flow[t];
        mincost+=flow[t]*dis[t];
        while(now!=s)
        {
            edge[last[now]].len-=flow[t];
            edge[last[now]^1].len+=flow[t];
            now=pre[now];
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    memset(head,-1,sizeof(head));
    int n,s,t;
    cin>>n;
    s=0;
    t=n+1;
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    sum/=n;
    cnt=0;
    for(int i=1; i<=n; i++)
    {
        if(a[i]>sum){
            addedge(s,i,a[i]-sum,0);
        }
        if(a[i]<sum){
            addedge(i,t,sum-a[i],0);
        }
        if(i>1){
            addedge(i,i-1,0x3f3f3f3f,1);
            addedge(i-1,i,0x3f3f3f3f,1);
        }
        else{
            addedge(i,n,0x3f3f3f3f,1);
            addedge(n,i,0x3f3f3f3f,1);
        }
        if(i<n){
            addedge(i,i+1,0x3f3f3f3f,1);
            addedge(i+1,i,0x3f3f3f3f,1);
        }
        else{
            addedge(i,1,0x3f3f3f3f,1);
            addedge(1,i,0x3f3f3f3f,1);
        }
    }
    mcmf(s,t);
    cout<<mincost<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注