Solution -「多校聯訓」數學考試

\(\mathcal{Description}\)

  Link.

  給定 \(n\) 個函數，第 \(i\) 個有 \(f_i(x)=a_ix^3+b_ix^2+cx_i+d~(x\in[l_i,r_i]\cap\mathbb Z)\)，還有 \(m\) 條形如 \(x_u\le x_v+d\) 的限制，請最大化 \(\sum_{i=1}^nf_i(x_i)\) 或聲明無解。

  \(n,|l_i|,|r_i|\le 100\)。

\(\mathcal{Solution}\)

  很久沒遇到了，壓根兒沒往網絡流方面想 qwq。

  對于每個 \(f_i\)，拉一條代表 \(f_i(l_i..r_i)\) 的鍊，邊權就是某個 \(f\) 的值的相反數；限制條件友善轉化為最小割，之後直接跑最小割即可。

  \(\mathcal O(\operatorname{Dinic}(\sum(r-l),m\sum(r-l)))\)。