Zkw费用流指针版

解题思路

这道题是想让所有节点最终货物值相等,也就是最终所有都会变成它们的平均值,所以可以使用费用流。

建图

  • 设$0$为超级源点,$n + 1$为超级汇点,平均值为$ave$
  • 对于每一个需要“送”的点,从$0$向它连边,容量$val_i - ave$,费用$0$
  • 对于每一个需要“拿”的点,从它向$n + 1$连边,容量$ave - val_i$,费用$0$
  • 从每个点向相邻点连容量$\infty$,费用$1$的边

代码

Zkw费用流,指针存图,有当前弧

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <algorithm>
#include <cstring>
#include <deque>
#include <cstdio>

using namespace std;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

int n;

struct Edge{
    int to, val, cost;
    Edge *next, *ops;
    Edge(int to, int val, int cost, Edge *next): to(to), val(val), cost(cost), next(next){}
};

Edge *head[MAXN], *cur[MAXN];

void AddEdge(int u, int v, int w, int c) {
    head[u] = new Edge(v, w, c, head[u]);
    head[v] = new Edge(u, 0, -c, head[v]);
    head[u]->ops = head[v]; head[v]->ops = head[u];
}

int s, t, res, ans;
int dis[MAXN];
bool vis[MAXN];

bool Spfa() {
    memset(dis, INF, sizeof(dis));
    memset(vis, false, sizeof(vis));
    deque<int> q; q.push_back(s); vis[s] = true; dis[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop_front();
        for (Edge *e = head[u]; e; e = e->next) {
            int v = e->to;
            if (e->val && dis[v] > dis[u] + e->cost) {
                dis[v] = dis[u] + e->cost;
                if (!vis[v]) {
                    if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
                    else q.push_back(v);
                }
            }
        }
    }
    return dis[t] < INF;
}

int Dfs(int u, int flow) {
    vis[u] = true;
    if (u == t) {
        res += flow;
        return flow;
    }
    int used = 0;
    for (Edge *&e = cur[u]; e; e = e->next) {
        int v = e->to;
        if ((v == t || !vis[v]) && e->val && dis[v] == dis[u] + e->cost) {
            int mi = Dfs(v, min(e->val, flow - used));
            if (mi) {
                used += mi;
                e->val -= mi;
                e->ops->val += mi;
                ans += e->cost * mi;
            }
            if (used == flow) break;
        }
    }
    return used;
}

void Dinic() {
    res = ans = 0;
    while (Spfa()) {
        vis[t] = true;
        while (vis[t]) {
            memset(vis, false, sizeof(vis));
            memcpy(cur, head, sizeof(head));
            Dfs(s, INF);
        }
    }
}

int num[MAXN];

int main() {
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int sum = 0;
    cin >> n;
    s = 0; t = n + 1;
    for (int i = 1; i <= n; i++) {
        cin >> num[i];
        sum += num[i];
    }
    int ave = sum / n;
    for (int i = 1; i <= n; i++) {
        if (num[i] > ave) AddEdge(s, i, num[i] - ave, 0);
        else AddEdge(i, t, ave - num[i], 0);
    }
    for (int i = 2; i <= n; i++) {
        AddEdge(i - 1, i, INF, 1);
        AddEdge(i, i - 1, INF, 1);
    }
    AddEdge(1, n, INF, 1);
    AddEdge(n, 1, INF, 1);
    Dinic();
    cout << ans << endl;
    return 0;
}