[ARC107F] Sum of Abs 题解-526互联

题意

给定一个 \(N\) 个点，\(M\) 条边的简单无向图，每个节点有两个值 \(A_i\) 和 \(B_i\)。

现对于每个节点，均可以选择花费 \(A_i\) 的代价将其删去或保留节点。若一个节点被删除，那么所有与其向连的边也会被删除。

定义一个极大联通块的权值为联通块内所有节点的 \(B_i\) 的和的绝对值，即 \(\left\lvert\sum B_i\right\rvert\)。定义整个图的权值为所有极大联通块的权值的和。

最大化操作后图的权值减去所有花费后的值。

\(1 \le N \le 300\)
\(1 \le M \le 300\)
\(1 \le A_i \le 10^6\)
\(-10^6 \le B_i \le 10^6\)

题解

可以发现每个节点有三种方式来产生贡献：

其所在联通块权值和为负，产生贡献 \(-B_i\)
其所在联通块权值和为正，产生贡献 \(B_i\)
其被删除，不产生贡献

那么我们可以通过对每个节点赋一个权值 \(C_i \in \left\{-1, 0, 1\right\}\) 来描述其产生的贡献，那么问题变为了最大化

\[\sum\limits_{i = 1}^{N}C_i \times B_i \]

可以发现一个联通块的内节点的权值 \(C_i\) 在除去 \(0\) 后一定相同，因此题目中的边的限制可以转化为：

对于任意一条边 \(\left(u, v\right)\)，不存在 \(C_u = 1 \land C_v = -1\) 或 \(C_u = -1 \land C_v = 1\)

考虑使用最小割来处理限制。

首先可以发现在不考虑限制的情况下最优价值为 \(\sum\limits_{i = 1}^{N}\left\lvert B_i \right\rvert\)，即 \(C_i\) 与 \(B_i\) 的正负性相同。

考虑将每个节点 \(i\) 拆分为网络中的两个节点 \(X_i\) 和 \(Y_i\)。建边 \(Y_i \rightarrow X_i\)，流量为 \(\infty\)。可以发现在此之后 \(X_i\) 和 \(Y_i\) 与源点 \(S\) 联通或是与汇点 \(T\) 联通的状态只有三种：\(\left(S, S\right)\), \(\left(S, T\right)\), \(\left(T, T\right)\)，考虑将 \(C_i\) 的三种可能值与之对应，有

\(C_i = 1 \Leftrightarrow \left(S, S\right)\)
\(C_i = 0 \Leftrightarrow \left(S, T\right)\)
\(C_i = -1 \Leftrightarrow \left(T, T\right)\)

接下来考虑如何建图。

首先对于每个节点：

若将其删除，那么需要花费的代价为 \(A_i + \left\lvert B_i \right\rvert\)。故可建边 \(X_i \rightarrow Y_i\)，流量为 \(A_i + \left\lvert B_i \right\rvert\)。
若 \(B_i > 0\)，那么 \(C_i = 1\) 对应的情况无需花费，若 \(C_i = -1\) 那么需要的花费为 \(2 \times \left\lvert B_i \right\rvert\)，可以建边 \(S \rightarrow X_i\)，流量为 \(2 \times \left\lvert B_i \right\rvert\)。
若 \(B_i < 0\)，那么 \(C_i = -1\) 对应的情况无需花费，若 \(C_i = 1\) 那么需要的花费为 \(2 \times \left\lvert B_i \right\rvert\)，可以建边 \(Y_i \rightarrow T\)，流量为 \(2 \times \left\lvert B_i \right\rvert\)。

接下来考虑如何处理边的限制。

对于边 \(\left(u, v\right)\)，建边 \(Y_u \rightarrow X_v\) 和 \(Y_v \rightarrow X_u\)，流量均为 \(\infty\)。

可以发现边的限制不合法当且仅当节点 \(u\) 和节点 \(v\) 的与源汇联通状态分别为 \(\left(S, S\right)\) 和 \(\left(T,T\right)\) 或 \(\left(T, T\right)\) 和 \(\left(S,S\right)\)，按上文建边可以避免这两种情况的出现。

\(\sum\limits_{i = 1}^{N}\left\lvert B_i \right\rvert\) 减去网络的最小割即为答案。

最终网络中的点数为 \(\mathcal{O}(N)\)，边数为 \(\mathcal{O}(N + M)\)。复杂度为 \(\mathcal{O}\left(N^2 \left(N + M\right)\right)\)，可以通过。

Code

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;

constexpr valueType INF = std::numeric_limits<valueType>::max();

class Dinic {
private:
    struct Edge {
    public:
        typedef std::list<Edge> container;
        typedef container::iterator iterator;

        valueType to;
        valueType cap;
        valueType flow;
        iterator pair;

        Edge() : to(-1), cap(-1), flow(-1), pair(){};

        Edge(valueType to, valueType cap, iterator pair = iterator()) : to(to), cap(cap), flow(0), pair(pair){};
    };

    typedef std::vector<Edge::container> Graph;
    typedef std::vector<Edge::iterator> IterVector;

    valueType N;
    Graph G;
    ValueVector depth;
    IterVector start;
    bool Initialized;

public:
    explicit Dinic(valueType N) : N(N), G(N + 1), depth(N + 1, 0), start(N + 1), Initialized(false){};

    void addEdge(valueType from, valueType to, valueType cap) {
        if (__builtin_expect(Initialized, false))
            throw std::runtime_error("Dinic: addEdge after init");

        G[from].emplace_back(to, cap);
        G[to].emplace_back(from, 0);
        G[from].back().pair = std::prev(G[to].end());
        G[to].back().pair = std::prev(G[from].end());
    }

    void init() {
        if (__builtin_expect(Initialized, false))
            throw std::runtime_error("Dinic: init twice");

        Initialized = true;

        std::fill(depth.begin(), depth.end(), 0);

        for (valueType i = 1; i <= N; ++i)
            start[i] = G[i].begin();
    }

    valueType maxFlow(valueType S, valueType T) {
        if (__builtin_expect(!Initialized, false))
            throw std::runtime_error("Dinic: maxFlow before init");

        valueType result = 0;

        while (bfs(S, T)) {
            IterVector begin = start;
            result += dfs(S, T, std::numeric_limits<valueType>::max(), begin);
        }

        return result;
    }

private:
    bool bfs(valueType S, valueType T) {
        std::fill(depth.begin(), depth.end(), 0);

        std::queue<valueType> Q;

        Q.push(S);
        depth[S] = 1;

        while (!Q.empty()) {
            valueType const u = Q.front();

            Q.pop();

            for (auto const &e : G[u]) {
                if ((e.cap > e.flow) && (!depth[e.to])) {
                    depth[e.to] = depth[u] + 1;
                    Q.push(e.to);
                }
            }
        }

        return depth[T] > 0;
    }

    valueType dfs(valueType u, valueType T, valueType flow, IterVector &Begin) {
        if (u == T || flow == 0)
            return flow;

        valueType result = 0;

        for (auto &e = Begin[u]; e != G[u].end(); ++e) {
            if (e->cap > e->flow && depth[e->to] == depth[u] + 1) {
                valueType const f = dfs(e->to, T, std::min(flow - result, e->cap - e->flow), Begin);

                e->flow += f;
                e->pair->flow -= f;

                result += f;

                if (result == flow)
                    return flow;
            }
        }

        return result;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N, M;

    std::cin >> N >> M;

    valueType const size = 2 * N + 2, S = 2 * N + 1, T = 2 * N + 2;

    Dinic dinic(size);

    ValueVector A(N + 1), B(N + 1), X(N + 1), Y(N + 1);

    for (valueType i = 1; i <= N; ++i) {
        X[i] = i;

        Y[i] = N + i;
    }

    for (valueType i = 1; i <= N; ++i)
        std::cin >> A[i];

    for (valueType i = 1; i <= N; ++i)
        std::cin >> B[i];

    for (valueType i = 1 ;i <= N; ++i) {
        dinic.addEdge(Y[i], X[i], INF);

        dinic.addEdge(X[i], Y[i], A[i] + std::abs(B[i]));

        if (B[i] > 0) {
            dinic.addEdge(S, X[i], 2 * std::abs(B[i]));
        } else {
            dinic.addEdge(Y[i], T, 2 * std::abs(B[i]));
        }
    }

    for (valueType i = 0; i < M; ++i) {
        valueType u, v;

        std::cin >> u >> v;

        dinic.addEdge(Y[u], X[v], INF);
        dinic.addEdge(Y[v], X[u], INF);
    }

    valueType sum = 0;

    for (valueType i = 1; i <= N; ++i)
        sum += std::abs(B[i]);

    dinic.init();

    std::cout << (sum - dinic.maxFlow(S, T)) << std::endl;

    return 0;
}