Luogu P4016 负载平衡问题

传送门qwq

刚学会网络流，把网络流24题按难度sort一下，第一个蓝题就不会...（某二分图匹配除外）

于是又跑去学了最小费用最大流。

听说网络流的难点就在于建图，似乎感受到一点了...

---

这道题和飞行员匹配一样，需要用到超级源点和汇点。

既然要平均分配，那么首先可以先算出平均值。

高于平均值的仓库一定有流出，低于的则有流入。

不能把每个高于平均值的都作为源点，所以把它们都连入源点s，容量为与平均值的差值，费用为0；反之亦然。

题中给出相邻的仓库运输费用为1，那么，将相邻的边之间连接容量为INF，费用为1的边。

注意，由于是双向边，所以1到2要建边，2到1也要建边。

剩下的就是最小费用最大流棵题了qwq

代码如下

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#define MogeKo qwq
using namespace std;

const int maxn = 2e5+10;
const int INF = 0x3f3f3f3f;
int n,m,s,t,cnt,avr,sum;
int a[maxn];
int head[maxn],to[maxn],nxt[maxn],w[maxn],co[maxn];
int fa[maxn],path[maxn],dis[maxn],fl[maxn];
int mincost;
bool vis[maxn];

void add(int x,int y,int ww,int cc) {
    to[cnt] = y;
    nxt[cnt] = head[x];
    head[x] = cnt;
    w[cnt] = ww;
    co[cnt] = cc;
    cnt++;
}

bool SPFA() {
    memset(dis,INF,sizeof(dis));
    memset(fl,INF,sizeof(fl));
    queue <int> q;
    dis[s] = 0;
    vis[s] = true;
    q.push(s);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = head[u]; i != -1; i = nxt[i]) {
            int v = to[i];
            if(dis[v] <= dis[u]+co[i] || !w[i]) continue;
            dis[v] = dis[u]+co[i];
            fa[v] = u, path[v] = i;
            fl[v] = min(fl[u],w[i]);
            if(!vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }
    if(dis[t] == INF) return false;
    return true;
}

void mcmf() {
    while(SPFA()) {
        for(int i = t; i != s; i = fa[i]) {
            int p = path[i];
            w[p] -= fl[t];
            w[p^1] += fl[t];
        }
        mincost += fl[t] * dis[t];
    }
}

int main() {
    scanf("%d",&n);
    memset(head,-1,sizeof(head));
    for(int i = 1; i <= n; i++) {
        scanf("%d",&a[i]);
        sum += a[i];
    }
    avr = sum/n;
    s = n+1,t = n+2;
    for(int i = 1; i <= n; i++) {
        a[i] -= avr;
        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);
    }
    add(1,n,INF,1), add(n,1,0,-1);
    add(n,1,INF,1), add(1,n,0,-1);
    for(int i = 1; i <= n; i++) {
        if(i-1 > 0) add(i,i-1,INF,1), add(i-1,i,0,-1);
        if(i+1 <= n) add(i,i+1,INF,1), add(i+1,i,0,-1);
    }
    n += 2;
    mcmf();
    printf("%d",mincost);
    return 0;
}