显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Who I am.

庸人只顾自我陶醉 Aftc、

 
 
 
 

日志分类

 
 
日志分类列表加载中...
 
 
 
 
 
 
 

浙江省 绍兴市 处女座

 发消息  写留言

 
博客等级加载中...
今日访问加载中...
总访问量加载中...
最后登录加载中...
 
 
 
 
 
 
 
 
 
 
 
网易云音乐 曲目表歌词秀
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
心情随笔列表加载中...
 
 
 
 
 

标签

 
 
数据加载中...
 
 
 
 
 
 
 
模块内容加载中...
 
 
 
 
 
 
 
我的关注列表加载中...
 
 
 
 
 
 
 
列表加载中...
 
 
 
 
 
 我要留言
 
 
 
留言列表加载中...
 
 
 
 
 
 
 
 

新博地址

2016-3-25 14:06:09 阅读22 评论0 252016/03 Mar25

http://aftc.github.io/

http://aftc.github.io/

http://aftc.github.io/

无聊的事情说三遍

作者  | 2016-3-25 14:06:09 | 阅读(22) |评论(0) | 阅读全文>>

终于要搬家了吗

2016-3-18 20:29:05 阅读21 评论0 182016/03 Mar18

本来想来一发题解,发现没有tex特么打个xx公式啊 卧槽

准备要搬家了= =

作者  | 2016-3-18 20:29:05 | 阅读(21) |评论(0) | 阅读全文>>

Network Flow

2015-4-10 21:26:33 阅读21 评论1 102015/04 Apr10

Studying Notes:

(零)

我是怀着十分激动的心情打这篇笔记的,也许这下意味着我真正脱离了普及组,成为水平更高一点的……蒟蒻了吧。

(一)

网络流是什么

它是一类关于有向图上流量的问题(不是手机流量= =),想必很多人都无意中在初中的数学竞赛中遇到过了,没错就是这么坑爹:

——感谢童施提供的真迹 OTZ。

就像上图所说,每条边有一个最大流量(即容量),有一源点S和一汇点T,网络流问题就是研究这样子的网络的性质,常见的有最大流问题,即求源汇最大流量。

由于水平/时间/篇幅有限,这篇东西只考虑最大流的一些解决方法,更多的东西以后补上。

残量网络

假设在一个流量图里,已经选了若干条边,在它们上面添加了流量:

每条边上,斜杠前的数是已有流量,斜杠后是边的容量。

我们发现以这个图现在的情况已经不能再加流量了,但是这并非是可以达到的最大流量。这说明了如果只是随心所欲地加一些流量的话,得到的答案也许不是最优解。

所以在情况不是最优时,我们应该加一个“回溯”的机制,也就是要能够“反悔”。

残量网络就因此被研究出来了,经研究发现,只要在每条流过的边上添一条“反向弧”就可以实现回溯:

上图就是第一张图的残量网络,红色的边是反向弧,黑色的边上面的数是剩余的容量,灰色的边已经被填满,剩余容量为0,因此不在残量网络中。

为什么呢?感性地想一想

作者  | 2015-4-10 21:26:33 | 阅读(21) |评论(1) | 阅读全文>>

查看所有日志>>

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017

注册 登录  
 加关注