wuvin
Always take risks!
Toggle navigation
wuvin
主页
实验室的搬砖生活
机器学习
公开的学术内容
公开的其他内容
About Me
归档
标签
友情链接
ZYQN
ihopenot
enigma_aw
hzwer
杨宗翰
2017-03-19 18:52:47
67
0
0
wuvin
对偶图 对偶图是建立在原有的平面图上的。 对于为什么叫“对偶”图，先看下度娘对于对偶的解释： 对偶是用字数相等、结构相同、意义对称的一对短语或句子来表达两个相对应或相近或意思相同的修辞方式。 自己可以看完对偶图的建图之后再来琢磨下这个句子，脑补一下“对偶”图的“对偶” 好了，说正事。 这是一张平面图 红线组成的是它的对偶图 什么？不知道怎么画？ 就是把面变成点，相邻的面连边。（所以每一条边都会跨国原有边界。） so,我们现有一个平面图 然后再找出图上所有面（还有最外面无限大的面） 然后，把面看成点 就像之前说的，相邻的面连边，蓝色与红色和紫色还有灰色相连（只有一个定点相同的不算，如绿色和蓝色） 然后连下去 就画好了 那么有什么用呢 比如最小割之类的啊 如果左上和右下分别为源点（S）和汇点（T），那么如果我们把外侧无限大的面分成两个 半面，（忽略无限大面自己之间的连线），构造对偶图，那么对偶图中灰蓝色点到灰紫色点的的任意一条路径都是原图的一个割。 因为对偶图中的边会跨过切只会跨过原图中的一条边。所以就可以在最短路的时间内跑最小割了。 例题传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2007
上一篇:
对偶图
下一篇:
OI 上路
0
赞
67 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
wuvin
没有帐号? 立即注册