警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「AtCoder」AGC031 E - Snuke the Phantom Thief

题意

传送门:AGC031 E - Snuke the Phantom Thief

给你一个 \(n\) 个点的点集 \(S\),和 \(m\) 条限制,第 \(i\) 个点 \((x_i,y_i)\) 有一个权值 \(v_i\)。你要选出一个集合 \(T\subseteq S\),最大化 \(\sum_{i\in T}i_v\),且满足所有的限制。限制有四种:

  • L a b\(\sum_{i\in T}[x_i\le a]\le b\)
  • R a b\(\sum_{i\in T}[x_i\ge a]\le b\)
  • D a b\(\sum_{i\in T}[y_i\le a]\le b\)
  • U a b\(\sum_{i\in T}[y_i\ge a]\le b\)

\(1\le n\le80,1\le x_i,y_i\le100,1\le v_i\le10^{15},1\le m\le320,1\le a_i\le100,0\le b_i<n\),且 \((x_i,y_i),(t_i,a_i),(t_i,b_i)\) 互不相同。

解法

毒瘤!

考虑加一条限制:\(|T|=k\)。然后枚举所有的 \(k\),选里面最大的。这样有助于转化限制:

  • L a b 转化为:\(T\) 中第 \(b+1\) 大的 \(x\) 大于 \(b\)
  • R a b 转化为:\(T\) 中第 \(k-b\) 大的 \(x\) 小于 \(b\)
  • D a b 转化为:\(T\) 中第 \(b+1\) 大的 \(y\) 大于 \(b\)
  • U a b 转化为:\(T\) 中第 \(k-b\) 大的 \(y\) 小于 \(b\)

于是对于 \(T\) 中的 \(k\) 个点中每个点的 \(x,y\),我们都可以得到一个上下界。我们令 \(T\) 中第 \(k\) 大的 \(x\) 的区间是 \([L_k,R_k]\)\(y\) 的区间是 \([D_k,U_k]\)

然后就是网络流套路了。

\(X(i)\) 为第 \(i\) 行的点,\(Y(i)\) 为第 \(i\) 列的点,\(X'(i)\)\(T\) 中第 \(i\) 大的 \(x\) 坐标的点,\(Y'(i)\)\(T\) 中第 \(i\) 大的 \(y\) 坐标的点。

  • 对于 \(S\) 中的每个点 \((x,y,v)\),连接 \(X(x)\xrightarrow{1,v}Y(y)\)
  • 对于 \(i\in[1,k]\) 中的每个 \(i\),将
    • \(X'(i)\) 连向 \(j\in[L_i,R_i]\) 中的每一个 \(X(j)\)
    • \(Y'(i)\) 连向 \(j\in[D_i,U_i]\) 中的每一个 \(Y(j)\)
    • \(S\) 连向 \(X'(i)\)
    • \(Y'(i)\) 连向 \(T\)

然后枚举 \(k\),跑 \(k\) 遍费用流就好了。

代码