题解：AT_arc107_f [ARC107F] Sum of Abs

chroneZ · 2024-11-29 17:17:10 · 题解

对于绝对值形式的贡献，考虑经典方法：将绝对值的贡献形式转写成 \max(x, -x) 的形式。因此本题可以等价地描述为，先支付一些代价删点，然后对删完点后的每个连通块 W，选择取 \sum \limits_{u \in W} b_u 或 -\sum \limits_{u \in W} b_u 加到最终答案中。

由此，除了删去的点，我们可以将点分为两类：b_i 取正的和 b_i 取负的，每个连通块内的点需属于同一类。可以想到用最小割处理。

假定最小割后与 S 连通的点 b_i 取负，与 T 连通的点 b_i 取正。显然答案具有上界 \sum |b_i|，考虑在此基础上分析点的分类对这个答案的影响：

• 点被删除：答案减少 a_u + |b_u|。

将每个点拆为 u_{\text{in}} 与 u_{\text{out}}，根据上文可以建立以下的最小割模型：

• 如果 b_u < 0，S 向 u_{\text{out}} 连流量为 2 |b_u| 的边。
• 如果 b_u > 0，u_{\text{in}} 向 T 连流量为 2 |b_u| 的边。
• 对于原图中存在的边 (u, v)，u_{\text{in}} 向 v_{\text{out}}，v_{\text{in}} 向 u_{\text{out}} 各连一条流量为 \infty 的边。

用 \sum |b_i| 减去得到的最小割即为答案。时间复杂度 \Theta(n^2(n + m))。

// Such a destiny was not desired.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int N = 600 + 50, M = 10000;
constexpr ll inf = 1e14, INF = 1e18;

struct NetFlow {
  struct Graph {
    int tot, h[N], cur[N], nxt[M], v[M]; ll cap[M], flow[M];
    Graph() {memset(h, -1, sizeof(h)); tot = 0;}
    inline void addEdge(int x, int y, ll z) {
      nxt[tot] = h[x], h[x] = tot;
      v[tot] = y, cap[tot] = z, flow[tot] = 0;
      tot++;
    }
  } G;
  inline void addEdge(int u, int v, ll cap) {
    G.addEdge(u, v, cap);
    G.addEdge(v, u, 0);
  }
  int n, S, T;

  int dep[N];
  bool bfs() {
    memset(dep, -1, sizeof(dep));
    queue<int> q; q.push(S); dep[S] = 0;
    while(q.size()) {
      int u = q.front(); q.pop();
      for(int i = G.h[u]; ~i; i = G.nxt[i]) {
        int v = G.v[i]; ll cap = G.cap[i], flow = G.flow[i];
        if(dep[v] == -1 && flow < cap) {
          dep[v] = dep[u] + 1;
          q.push(v);
        }
      }
    }
    return (dep[T] != -1);
  }

  ll dfs(int u, ll F) {
    if(u == T || !F) return F;
    ll p = 0;
    for(int &i = G.cur[u]; ~i; i = G.nxt[i]) {
      int v = G.v[i]; ll cap = G.cap[i], flow = G.flow[i];
      if(dep[v] == dep[u] + 1) {
        ll t = dfs(v, min(F, cap - flow));
        F -= t, p += t;
        G.flow[i] += t, G.flow[i ^ 1] -= t;
      }
      if(!F) break;
    }
    return p;
  }

  ll res;
  ll dinic() {
    while(bfs()) {
      memcpy(G.cur, G.h, sizeof(G.h));
      res += dfs(S, INF);
    }
    return res;
  }
} F;

int n, m; ll a[N], b[N];

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

  cin >> n >> m;
  for(int i = 1; i <= n; i++) cin >> a[i];
  for(int i = 1; i <= n; i++) cin >> b[i];

  F.S = 0, F.T = 2 * n + 1, F.n = F.T;
  for(int i = 1; i <= n; i++) {
    F.addEdge(i, i + n, a[i] + abs(b[i]));
    if(b[i] < 0) F.addEdge(F.S, i, 2 * abs(b[i]));
    if(b[i] > 0) F.addEdge(i + n, F.T, 2 * abs(b[i]));
  }

  for(int i = 1; i <= m; i++) {
    int u, v; cin >> u >> v;
    F.addEdge(u + n, v, inf);
    F.addEdge(v + n, u, inf);
  }

  ll ans = 0;
  for(int i = 1; i <= n; i++) ans += abs(b[i]);
  cout << ans - F.dinic() << "\n";
}