题意
给定一个 \(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;
}