@2368860385
2020-11-07T03:00:45.000000Z
字数 1074
阅读 160
前：day2上午——网络流
衢州
2018.7.29
平面图
T1 NOI 2010 海拔
平面图最小割。
从左下到右上求最大流。
每个点只能是0/1，而且每个点的四周不能都比它小或大，所以最后的图是1构成一个联通块，0构成一个联通块，把图分成两部分，然后找一条割即可，把原图割成两部分。
注意到每个边有方向，需要处理一下。
T2 TCO SemiFinal Colorful Tree
平面图最小割
最大权闭合子图
T3 完美理论
51nod1325 两棵树的问题
枚举一个根，那么选一个点，它的父亲也要选。
T4 SRM577Hard BoardPainting
两个相邻的点连在一起，如果一起选，就会获得一的代价。
即一个点获得1的代价，要求选两个连在的点。
另一种做法？
黑白染色
集合划分
T1 SRM594Medium FoxAndGo3
http://topcoder.g.hatena.ne.jp/agw/20131023
注意：任意白子不相邻
如果让一个白子变成空格，那么它相邻的空格都不能选了。
二分图，左边是白子，右边是空格，每个白子与相邻的空格连边，表示选了这个白子，不能选哪些空格，选了空格，不能再选白子。最大点独立集。
T2 最优选择
按位处理。
由于只有01不同的点才会产生代价，那么我们自然的想到了最小割，也就是使01不同的边尽量少。
建立虚拟源汇st，en。将st向所有已经标为0的点连容量为无穷的边，从所有已经标为1的点向en连容量为无穷的边，对于原图的每一条边都变成一条新的流量为1的双向边。对于这个图，求出其最小割，则与源点在同一个割集的点填0，与汇点在同一个割集的点填1即可。
T3 SRM 558 ard Surrounding Game
离散变量模型
• 离散变量型网络流一般解决如下问题：
• 每个变量有若干个不同的取值 A = 0,1,2,⋯, A并且两个变量之间会对代价产生贡献。
• 一般贡献会和两个变量的差有关。
• 建图方式一般为，对一个点𝑥 A ，拆𝑚 A + 1个点并连成从𝑆到𝑇的链，割哪一
条边就代表取哪个值，贡献用两条链之间的连边表达。
