负载平衡问题

中位数法

更详细的解法,看这里:

如上图

$a_i$ : 表示从 $x_i$ 移动数量 $a_i$ 的货物到 $x_{i+1}$
- 注意 : $a_i > 0$ 表示, 从 $x_i$ 移动 $x_{i+1}$
- $a_i < 0$ 表示, 从 $x_{i+1}$ 移动 $x_{i}$
假设 $a_0$ 已知: 那么总体的

代码

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-30 21:08:00
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
int n,m;
ll tot;
ll x[maxn]; // 每个元素
ll avg;
ll t[maxn]; // t[i] = x_i - avg;
ll s[maxn]; // t[i] 前缀和

ll _abs(ll t) {
    if( t < 0) t *=-1;
    return t;
}


int idx(int i) {
    return i % n;
}

void init(){
    std::cin >> n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        
        //这个id可以不要
        // 但是为了能对应解析的设定
        int id = idx(i); 

        std::cin >> x[id];
        tot+=x[id];
    }
    avg = tot / n;

}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    init();
    for(int i = 0;i < n ;++i ) 
        t[i] = x[i] - avg;

    s[0] = t[0];
    for(int i = 1;i < n ;++i ) // i: 1->n-1
    {
        s[i] = s[i-1] + t[i];
    }

    //排列
    std::sort(s,s+n);

    // 这里为什么n-1,因为 下标从0开始了
    int k = (n-1)/2;

    ll ans = 0;
    for(int i = 0;i <= n-1 ;++i ) // i: 0->n-1
    {
        ans += _abs( s[i] - s[k]);
    }
    std::cout << ans << endl;
    
    return 0;
}

网络流法

思想:

我们把点想象成蓄水池,边(车)想象成管道, 水位高的通过管道流动到水位低的地方,最终所有的水池都会达到avg.

对于 $x_i > avg$ 的点,最终的状态一定是avg
对于 $x_i < avg$ 的点,最终的状态一定是avg

那么怎么计算如何流动使得管道的流动的水流的绝对值最小?

可以想到: 在管道上流动水量1,就得到费用1,这显然是费用流. 哪就去求最小费用流MCMF

1. 建模思路：供需平衡

我们将仓库分为两类：

供过于求（ $x_i > avg$ ）： 这些仓库是“源点”，需要把多余的货物送出去。
供不应求（ $x_i < avg$ ）： 这些仓库是“汇点”，需要接收货物。

$x_i < avg$ 最终一定要得到 $avg - x_i$ ,也就是说可以看成 : 得到 -> 消失 -> 漏掉了

这显然是一个多源多汇的题

2. 建图规则

我们需要建立一个超级源点 $S$ 和一个超级汇点 $T$ 。

第一类：连接源汇点

如果 $x_i - avg > 0$ ，从 $S$ 向仓库 $i$ 连一条边：
- 容量： $x_i - avg$
- 费用： $0$ （从源点拿取货物本身没有代价）
如果 $x_i - avg < 0$ ，从仓库 $i$ 向 $T$ 连一条边：
- 容量： $avg - x_i$
- 费用： $0$ （货物到达目的地，不再产生运输代价）

第二类：仓库之间的运输（环形逻辑）

由于相邻仓库可以互相运输，且每搬运 1 单位货物花费 1：

对于每个仓库 $i$ ，向相邻的 $i+1$ 和 $i-1$ 连边（注意环形，即 $1$ 和 $n$ 相连）：
- 容量： $\infty$ (或者一个足够大的数)
- 费用： $1$

3. 算法执行

在建好的图上跑一次 最小费用最大流（MCMF）：

最大流保证了所有仓库最终都能达到 $avg$ （因为总盈余等于总亏空）。
最小费用则保证了搬运量最少。

4. 示例说明

假设 3 个仓库，库存分别为 17, 9, 4，平均数 $avg = 10$ 。

仓库 1: 盈余 7。连边 $(S, 1, cap:7, cost:0)$
仓库 2: 亏空 1。连边 $(2, T, cap:1, cost:0)$
仓库 3: 亏空 6。连边 $(3, T, cap:6, cost:0)$
仓库间连边： $(1 \leftrightarrow 2), (2 \leftrightarrow 3), (3 \leftrightarrow 1)$ ，费用均为 1。

代码

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-30 21:57:32
 * Modified for Min-Cost Max-Flow
 */

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5; // 点
const int maxe = 2e6+5; // 边 (注意：要是题目边数的2倍)
const long long INF = 1e18;
const int INF_INT = 0x3f3f3f3f;
typedef  long long ll;
int n,m;
int s,t; // 源点 汇点
ll x[maxn];

// 存图的模板

//oisnip_begin code/graph/linklist.cpp 内容开始

struct linkList {
    // 修改点1: 增加 c (cost) 字段
    typedef struct {int u,v,w,c,next;} edge; 
    edge e[maxe];
    int h[maxn],edge_cnt=0;
    linkList(){
        reset();
    }

    void reset() {
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }

    // 修改点2: add 增加 cost 参数
    void add(int u,int v,int w=0, int c=0){
        e[edge_cnt] = {u,v,w,c,h[u]};
        h[u] = edge_cnt++;
    }
    
    //下标访问
    edge& operator[](int i){ return e[i]; }
} e;

//oisnip_end code/graph/linklist.cpp 内容结束


// MCMF 算法模板 - 基于linkList存图
// 最小费用最大流
struct MCMF {
    int dis[maxn];   // SPFA 最短路（最小费用）
    int flow[maxn];  // 到达当前节点的最小流量限制
    int pre[maxn];   // 记录路径：前驱节点
    int last[maxn];  // 记录路径：前驱边
    bool vis[maxn];  // SPFA 队列标记
    int n;           // 节点数
    
    long long max_flow;
    long long min_cost;

    void init(int n) {
        // 重置linkList
        e.reset();
        this->n = n;
    }
    
    // 添加边：从u到v，容量为cap，单位费用为cost
    void addEdge(int u, int v, int cap, int cost) {
        e.add(u, v, cap, cost);      // 正向边：容量cap，费用cost
        e.add(v, u, 0, -cost);       // 反向边：容量0，费用-cost
    }
    
    // SPFA 寻找单位费用最小的增广路
    // 返回是否能到达汇点
    bool spfa(int s, int t) {
        // 初始化
        for(int i = 0; i <= n+1; i++) dis[i] = INF_INT, vis[i] = 0, flow[i] = INF_INT;
        
        queue<int> q;
        dis[s] = 0;
        vis[s] = 1;
        pre[t] = -1; // 标记汇点前驱，用于判断是否可达
        q.push(s);
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            vis[u] = 0;
            
            // 使用linkList的遍历方式
            for(int i = e.h[u] ; ~i ;i = e[i].next) {
                int v = e[i].v;
                int cap = e[i].w;
                int cost = e[i].c;

                // 如果有残余容量 且 路径费用更小
                if (cap > 0 && dis[v] > dis[u] + cost) {
                    dis[v] = dis[u] + cost;
                    pre[v] = u;    // 记录前驱节点
                    last[v] = i;   // 记录前驱边
                    flow[v] = min(flow[u], cap); // 更新路径上的最小流量限制
                    
                    if (!vis[v]) {
                        vis[v] = 1;
                        q.push(v);
                    }
                }
            }
        }
        
        return pre[t] != -1;
    }
    
    // 计算 最小费用 & 最大流
    // 结果保存在成员变量 max_flow 和 min_cost 中
    // 也可以修改函数返回 pair<long long, long long>
    void solve(int s, int t) {
        max_flow = 0;
        min_cost = 0;
        
        // 只要还能找到费用最小的路径（SPFA），就继续增广
        while (spfa(s, t)) {
            int now = t;
            int f = flow[t]; // 本次增广的流量
            
            max_flow += f;
            min_cost += (long long)f * dis[t];
            
            // 回溯更新残留网络
            while (now != s) {
                int edge_idx = last[now]; // 当前边的下标
                
                e[edge_idx].w -= f;       // 正向边容量减少
                e[edge_idx ^ 1].w += f;   // 反向边容量增加
                
                now = pre[now]; // 向前移动
            }
        }
    }
} mcmf;

void init(){
    std::cin >> n;
    s = 0;
    t = n+1;

    mcmf.init(t +5); // 注意这里可能需要根据节点编号调整大小，例如 n+2
    ll tot = 0;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        std::cin >> x[i];
        tot += x[i];

    }
    ll avg = tot / n;
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        if( x[i] > avg)
            mcmf.addEdge(s, i, x[i]-avg, 0);
        else if( x[i] < avg)
            mcmf.addEdge(i, t, avg-x[i], 0);
    }
    
    for (int i = 1; i < n; i++) {
        mcmf.addEdge(i, i+1, INF_INT, 1); 
        mcmf.addEdge(i+1, i, INF_INT, 1); 
    }
    mcmf.addEdge(n, 1, INF_INT, 1);
    mcmf.addEdge(1, n, INF_INT, 1);
}

// 使用示例：
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    init();
    
    mcmf.solve(s, t);
    
    cout <<  mcmf.min_cost << "\n";
    
    return 0;
}

/*
复杂度分析：
- 时间复杂度：基于SPFA的MCMF算法，复杂度为 O(k * E * F)，其中 F 是最大流，k 是常数（SPFA平均复杂度）。
- 空间复杂度：O(V + E)

使用说明：
1. 创建实例：MCMF mcmf;
2. 初始化：mcmf.init(n);
3. 添加边：mcmf.addEdge(u, v, cap, cost);
4. 求解：mcmf.solve(s, t);
5. 获取结果：mcmf.max_flow 和 mcmf.min_cost

注意事项：
- 节点编号：确保 init(n) 中的 n 覆盖了所有节点编号（建议传 max_node_index）。
- 费用类型：如果费用可能很大，注意 min_cost 使用 long long。
- 负费用：SPFA 可以处理负费用边，但图中不能有负权回路。
*/

目录