ghj1222又更新博客了。尽管不能做到高产似母猪，但是最近又开始想更新了。
学网络流这么长时间了，才知道有最大权闭合子图这种科技，我真是太菜了。
什么是最大权闭合子图？
给定一个DAG（好像是DAG？？大雾），每个点有权值（可正可负），要求钦定图中的一些点，满足：
求最大点权。
解法：考虑网络流建图。
然后从src到dest跑最大流，答案为所有正点权的和减去最大流。
原理：根据最大流最小割定理，我们跑出的最大流就相当于最小割。
考虑从src到dest的某一条路径。路径的形式一定是由src到某个正权值点，再到某个负权值点，再到dest。中途容量为inf的边在最小割中肯定是不会被切断的，所以只有两种情况：
其实网络流模型不难理解，稍微动动脑即可。
例题：[SHOI2017]寿司餐厅
题意特别恶心。我们对于某个区间[l,r]建立一个点，发现我们选择[l,r]就必须选择[l+1,r]和[l,r-1]，选择区间就必须选择所有寿司（从而购买之），选择寿司就得选择那个寿司对应的mx^2
所以对于满足l<r的[l,r]向[l+1,r]和[l,r-1]连边，点权即为输入值；
对于[i,i]向寿司i连边，[i,i]点权为输入值，寿司i的点权为寿司i花费，注意是负的；
对于寿司i再向a[i]代号连边，对于某个代号j，点权为-mj^2
然后对于这个图跑最大权闭合子图即可。代码太丑，不放了。
原文：https://www.cnblogs.com/oier/p/10222256.html