专栏文章

题解：AT_arc107_f [ARC107F] Sum of Abs

cchroneZLuminous
AT_arc107_f题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqy85bp
此快照首次捕获于
2025/12/04 12:41
3 个月前
此快照最后确认于
2025/12/04 12:41
3 个月前
查看原文
对于绝对值形式的贡献，考虑经典方法：将绝对值的贡献形式转写成 max⁡(x,−x)\max(x, -x) 的形式。因此本题可以等价地描述为，先支付一些代价删点，然后对删完点后的每个连通块 WW，选择取 ∑u∈Wbu\sum \limits_{u \in W} b_u 或 −∑u∈Wbu-\sum \limits_{u \in W} b_u 加到最终答案中。
由此，除了删去的点，我们可以将点分为两类：bib_i 取正的和 bib_i 取负的，每个连通块内的点需属于同一类。可以想到用最小割处理。
假定最小割后与 SS 连通的点 bib_i 取负，与 TT 连通的点 bib_i 取正。显然答案具有上界 ∑∣bi∣\sum |b_i|，考虑在此基础上分析点的分类对这个答案的影响：
  • 点被删除：答案减少 au+∣bu∣a_u + |b_u|。
  • bu<0b_u < 0 的点被划分给 TT：答案减少 2∣bu∣2|b_u|。
  • bu>0b_u > 0 的点被划分给 SS：答案减少 2∣bu∣2|b_u|。
将每个点拆为 uinu_{\text{in}} 与 uoutu_{\text{out}}，根据上文可以建立以下的最小割模型：
  • uoutu_{\text{out}} 向 uinu_{\text{in}} 连流量为 au+∣bu∣a_u + |b_u| 的边。
  • 如果 bu<0b_u < 0，SS 向 uoutu_{\text{out}} 连流量为 2∣bu∣2 |b_u| 的边。
  • 如果 bu>0b_u > 0，uinu_{\text{in}} 向 TT 连流量为 2∣bu∣2 |b_u| 的边。
  • 对于原图中存在的边 (u,v)(u, v)，uinu_{\text{in}} 向 voutv_{\text{out}}，vinv_{\text{in}} 向 uoutu_{\text{out}} 各连一条流量为 ∞\infty 的边。
用 ∑∣bi∣\sum |b_i| 减去得到的最小割即为答案。时间复杂度 Θ(n2(n+m))\Theta(n^2(n + m))。
CPP
// 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";
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...