题解 - P4016 负载平衡问题

· · 个人记录

题目传送门

题意：给定n个数，求最少移动（只能相邻）多少，可以使每个数相同。

网络流-最小费用流。

最大网络流保证方案正确性，最小费用保证可行。

我们考虑每个数减去平均值，若为正数，则从超级源点连一条a[i]距离为0的边，表示此点要分出a[i]的流。 反之，则连向超级汇点，表示要吸收a[i]的流，再按照题意相邻的边连一条无限流，价格为1的边即可。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int fl[50000],dis[50000],last[50000],pre[50000];
int n,m,ans,a[50000],tot=1,S,T;
int head[50000],go[50000],nex[50000],w[50000],d[50000],maxflow,mincost,vis[50000];
void add(int u,int v,int flow,int cost)
{
    nex[++tot]=head[u];
    head[u]=tot;
    go[tot]=v;
    w[tot]=flow;
    d[tot]=cost;
}
bool spfa()
{
    memset(vis,0,sizeof(vis));
    memset(dis,0x7f,sizeof(dis));
    memset(fl,0x7f,sizeof(fl));
    queue <int> q;
    q.push(S);
    dis[S]=0;
    vis[S]=1;
    pre[T]=-1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=nex[i])
        {
            int v=go[i];
            if(w[i]>0&&dis[v]>dis[u]+d[i])
            {
                dis[v]=dis[u]+d[i];
                fl[v]=min(fl[u],w[i]);
                pre[v]=u;
                last[v]=i;
                if(vis[v]==0) 
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return pre[T]!=-1;
}
signed main()
{
    int sum=0;
    cin>>n;
    S=0,T=n+1;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    sum/=n;
    for(int i=1;i<=n;i++)
    {
        a[i]-=sum;
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]>0) add(S,i,a[i],0),add(i,S,0,0);
        if(a[i]<0) add(i,T,-a[i],0),add(T,i,0,0);
    }
    for(int i=1;i<=n;i++)
    {
        if(i!=1) add(i,i-1,1e9,1),add(i-1,i,0,-1);//注意建反边时流为0，代价为-dis。 
        if(i!=n) add(i,i+1,1e9,1),add(i+1,i,0,-1);
    }
    add(1,n,1e9,1),add(n,1,0,-1);
    add(n,1,1e9,1),add(1,n,0,-1);
    while(spfa())
    {
    //  cout<<fl[T]<<" "<<dis[T]<<endl;
        maxflow+=fl[T];
        mincost+=dis[T]*fl[T];
        int now=T;
        while(now!=S)
        {
            w[last[now]]-=fl[T];
            w[last[now]^1]+=fl[T];
            now=pre[now];
        }
    }
    cout<<mincost;
    return 0;
}