ARTICLE DETAIL

资讯详情

深耕网站建设、视觉设计与SEO优化的一线实战洞察。

9.20 模拟赛 T4

9.20 模拟赛 T4

题意:有 \(n\) 个点,每个点有四个属性 \(a_i,b_i,c_i,v_i\)。现在要在这 \(n\) 个点之间连无向边。要求:

  • \(i\) 的度数至少为 \(a_i\)
  • \(i\) 的所有邻居 \(j\)\(v_j\),要么都小于等于 \(v_i\),要么都大于等于 \(v_i\)
    当小于等于的时候,\(i\) 这个点的收益为 \(b_i\);大于等于的时候,收益为 \(c_i\)。如果邻居的 \(v_j\) 值全部等于 \(v_i\),那么收益为 \(\max(b_i,c_i)\)

最大化收益,或报告无解。
\(1 \le n \le 400,0 \le a_i \le n, 1 \le v_i \le n, 0 \le b_i,c_i \le 10^9\)

返回列表