题目描述

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

输入格式

文件的第 11 行中有 11 个正整数 nn，表示有 nn 个仓库。
第 22 行中有 nn 个正整数，表示 nn 个仓库的库存量。

输出格式

输出最少搬运量。

输入

5
17 9 14 16 4

输出

11

这道题很容易看出是一道最小费用最大流问题， 当然也可以用数学加贪心的方法过题，

#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>
#include<queue>

using namespace std;

const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;

struct Edge
{
    int to, w, f, next;
}edg[MAXN];

int head[MAXN], vis[MAXN], pre[MAXN], last[MAXN], dis[MAXN], flow[MAXN], cnt = 0;

void Init()
{
    memset(head, -1, sizeof(head));
    cnt = 0;
}

void Add_edge(int u, int v, int w, int f)
{
    edg[cnt].w = w;
    edg[cnt].to = v;
    edg[cnt].f = f;
    edg[cnt].next = head[u];
    head[u] = cnt++;
    edg[cnt].w = 0;
    edg[cnt].to = u;
    edg[cnt].f = -f;
    edg[cnt].next = head[v];
    head[v] = cnt++;
}

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

int Mincost(int s, int t)
{
    int mincost = 0;
    while(SPFA(s, t))
    {
        mincost += dis[t] * flow[t];
        int now = t;
        while(now != s)
        {
            edg[last[now]].w -= flow[t];
            edg[last[now]^1].w += flow[t];
            now = pre[now];
        }
    }
    return mincost;
}

int main()
{
    int n, num[MAXN], sum = 0, ans = 0;
    scanf("%d", &n);
    Init();
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d", &num[i]);
        sum += num[i];
    }
    sum /= n;
    int s = 208, t = 209;
    for(int i = 1; i <= n; ++i)
        num[i] -= sum;
    for(int i = 1; i <= n; ++i)
    {
        if(0 > num[i])
        {
            Add_edge(i, t, -num[i], 0);
        }
        else if(0 < num[i])
        {
            Add_edge(s, i, num[i], 0);
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        if(i != 1)
            Add_edge(i, i - 1, INF, 1);
        if(i != n)
            Add_edge(i, i + 1, INF, 1);
    }
    Add_edge(1, n, INF, 1);
    Add_edge(n, 1, INF, 1);
    printf("%d\n", Mincost(s, t));
}