P4016 负载平衡问题

@[toc]
P4016 负载平衡问题

题目描述

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

输入格式

第一行一个正整数 n，表示有 n 个仓库。

第二行 n 个正整数，表示 n 个仓库的库存量。

输出格式
输出最少搬运量。

输入输出样例
输入 #1复制

5
17 9 14 16 4

输出 #1复制

11

说明/提示
1≤n≤100。

题解：

和网络流啥关系。。。又是老婆饼里没老婆？

方法一：

环形均分纸牌问题，还是板子题，代码都是通用的。。

贪心+数论
这种题总感觉在哪见过。。。
我们先考虑一种弱化的题目
n个仓库排成一列，每个仓库都有一定数量货物a[i]，只能相邻仓库可以传递货物，问最少需要传递几次才可以使各仓库货物相等？（就是把原题中的环改成一个列）
总数为sum，平均每个仓库分到T=sum/n，b[ i ]= T - a[ i ] ( b[]表示距离标准还有多少)，只要b[i]>0就说明后面一定有b[x]<0,那当前i多余的货物就向后移动，其实也就是多退少补，最终移动总牌数
现在的问题是n个仓库围成一个圈，我们可以通过破圈成链来解决这个问题。环形均分纸牌问题可以发现一个性质：至少有两个仓库是不需要从彼此之间那得到卡牌，这样就可以从这两点破坏成链
如果这种方式不明白，可以看我的这个题解，有详细分析解答
博客讲解

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
const int maxn=1e6+4;
ll a[maxn];
int main()
{
    cin>>n;
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    sum/=n;
    for(int i=n;i>1;i--)
    {
        a[i]=sum-a[i]+a[i+1];//为啥是这个公式可以在我那个推到里面得到 
    }
    a[1]=0;
    sort(a+1,a+n+1);
    ll res=0;
    int mid=(n+1)/2;
    for(int i=1;i<=n;i++)
    {
        res+=abs(a[i]-a[mid]);
    } 
    cout<<res<<endl;
    return 0;

} 

方法二：

恕我才疏学浅真的是一道最小费用最大流的题目
1.源点是0，汇点是n+1，费用是指两个相邻仓库中的运输单价
2.为了让所有仓库都均等，我们就要让多的仓库送出货物，连向源点；少的仓库就要接受货物，连向汇点。且连接源汇点的费用是0
3.相邻的仓库之间依次连上一条容量为 INF ，花费为 1 的双向边，
4.因为存在环的情况，所以还要特别处理1号节点与n号节点
我们用样例做一下分析：

每个边都有两种颜色数字，一个表示花费，一个表示容量
源点为起点的边容量之和等于以重点为边容量之和
跑一边费用流就可以了

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 5001;
const int MAXM = 50001;
const int INf = 2147483647;
int n, m, s, t, edge_sum = 1;
int maxflow, mincost;
int dis[MAXN], head[MAXN], incf[MAXN], pre[MAXN];
int a[MAXN];
bool vis[MAXN];
struct Edge {
    int next, to, dis, flow;
}edge[MAXM << 1];
inline void addedge(int from, int to, int flow, int dis) {
    edge[++edge_sum].next = head[from];
    edge[edge_sum].to = to;
    edge[edge_sum].dis = dis;
    edge[edge_sum].flow = flow;
    head[from] = edge_sum;
}
inline bool spfa() {
    queue <int> q;
    memset(dis, -1, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    q.push(s);
    dis[s] = 0;//距离 
    vis[s] = 1;// 记录该点已询问过 
    incf[s] = 0x7fffffff;//记录路径上的最小流 
    while(!q.empty()) {
        int u = q.front();
        vis[u] = 0;
        q.pop();
        for(register int i = head[u]; i; i = edge[i].next) {
            if(!edge[i].flow) continue;
            int v = edge[i].to;
            if(dis[v] > dis[u] + edge[i].dis||dis[v]==-1) {
                dis[v] = dis[u] + edge[i].dis;
                incf[v] = min(incf[u], edge[i].flow);
                pre[v] = i;//记录前缀点 
                if(!vis[v])
                {
                    vis[v] = 1;
                    q.push(v);
                 } 
            }
        }
    }
    if(dis[t] == -1) return 0;
    return 1;
}
inline void EK() {
    while(spfa()) {
        int x = t;
        maxflow += incf[t];
        mincost += dis[t] * incf[t];
        int i;
        while(x != s) {
            i = pre[x];
            edge[i].flow -= incf[t];
            edge[i^1].flow += incf[t];//建立反向边 
            x = edge[i^1].to;
        }
    }
}
int main() {
    scanf("%d", &n);
    int sum = 0;
    for(register int i = 1; i <= n; ++i) 
    {
        scanf("%d",&a[i]);
        sum += a[i];
    }
    sum /= n;//算出平均值
    for(register int i = 1; i <= n; ++i) {
        if(a[i] < sum) {//如果需要运入就与s连边
            addedge(0, i, sum - a[i], 0);
            addedge(i, 0, 0, 0);
        } 
        else if(a[i] > sum) {//如果需要运出就与t连边
            addedge(i, n + 1, a[i] - sum, 0);
            addedge(n + 1, i, 0, 0);
        }
        //以上为与S，T相连，以下为与临点相连 
        if(i == 1) {//特判1,别忘了是无向图
            addedge(1, n, INf, 1);
            addedge(n, 1, 0, -1);
            addedge(n, 1, INf, 1);
            addedge(1, n, 0, -1);
        } 
        else {
            addedge(i-1, i, INf, 1);
            addedge(i, i-1, 0, -1);
            addedge(i, i-1, INf, 1);
            addedge(i-1, i, 0, -1);
        }
    }
    s = 0, t = n + 1;
    EK();
    printf("%d\n",mincost);
    return 0;
}