bzoj 4873 [Shoi2017]寿司餐厅

Posted by

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=4873

题解

最大权闭合子图,源点向所有权值为正的区间\([i,j]\)连边,容量为\(d[i][j]\),所有权值为负的区间\([i,j]\)向汇点连边,容量为\(-d[i][j]\);

所有表示代号的节点\(x\)向汇点连边,容量为\(mx^2\),所有区间\([i,i]\)向表示该点代号的节点连边,容量为\(INF\),所有区间\([i,i]\)向汇点连边,容量为该点的代号\(x\);

最后,由于选择了\([i,j]\)就一定选择了\([i+1,j]\)和\([i,j-1]\),故所有\(i < j\)的区间\([i,j]\)向区间\([i+1,j],[i,j-1]\)连边,容量为\(INF\);

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注