Day2 AM 网络流

正睿OI

一个整理：https://blog.csdn.net/qq_31918005/article/details/81268671

最小割

NOI2010 海拔

https://www.cnblogs.com/SovietPower/p/9534702.html

TCO

$Description$
　　
$Solution$
　　

最大权闭合子图

完美理论

$Description$
　　
$Solution$
　　

SRM577

$Description$
　　
$Solution$
　　

黑白染色 集合划分模型

SRM594

$Description$
　　
$Solution$
　　

最优选择

$Description$
　　
$Solution$
　　

SRM558

$Description$
　　
$Solution$
　　

离散变量模型

SRM590

$Description$
　　
$Solution$
　　

SRM627

$Description$
　　
$Solution$
　　

BJOI2016 水晶

$Description$
　　
$Solution$
　　

流量分配

SCOI2016 奇怪的游戏

$Solution$
这种题当然要黑白染色。。
两种颜色的格子数可能相同，也可能差1。记n1/n2为黑/白格子数，s1/s2为黑/白格子权值和。
如果n1!=n2，假设n1>n2，因为每次是同时给两种颜色+1，所以最后的差也只能是s1-s2(s1>s2)，个数只差1，所以也只能都变成s1-s2。(注意s1-s2>=A_{max})
如果n1==n2，假设x合法，那么x+1也合法，因为黑白可以两两配对并加一。即可以二分。
二分图匹配模型，二分后边的容量就可以确定了。最大流是(x*tot-s1-s2)/2或者源点汇点都满流则合法。
那个。。上限是$A_{max}$么。。显然不是啊。
https://www.cnblogs.com/SovietPower/p/9587738.html

Turning Railways

$Description$
　　
$Solution$
　　

SRM575

$Description$
　　
$Solution$
　　

清华集训

$Description$
　　
$Solution$
　　

匹配与扩展

流量平衡

消负环

欧拉回路

上下界网络流

一维差分模型

线性规划 对偶原理