网络流
27/08/2007今天, 我无耻地做了一名逃兵. 结论是我的人权主义思想是完全不适应这个社会的. 我打算慢慢地学会以一个野人的角度看待问题, 免得与我们的社会产生更大的冲突, 使得自己痛不欲生接而再令别人痛不欲生. 具体内容, 当军训结束后, 会另写一篇文章.
在逃亡日, 我总结了这些天来( 一个月了吧 )对网络流的感触. 由于战略安排, 我的网络流学习效率十分低下. 但不管怎么说, 我学到了很多. 教材是CLRS.
流, 形象地说, 就是水流在一个水管网络中行进的量与路径. 最大流, 就是能够将水流尽可能多地从s运往t的一种流, 即流的值最大. 流有容量限制, 反对称性, 流守恒性这三个性质. 容量限制, 就是通过水管的水流不能把水管给撑爆了, 它得低于水管的流量限制. 反对称性, 即水管从左向右运过来x单位的水, 我认为有更好的运送方案, 所以我可以将不超过x的水再沿这个水管从右到左给它送回去. 流守恒性, 水流在通过这个网络时, 不可以消失, 不可以增加. 即只有自来水公司可以供水, 只有下水道可以消耗水( “永远”地占有水 ), 而各位用户和传输用的管道没有产生水的能力, 也没有将水据为己有的权力,他( 它 )们必须把这些水流原封不动地传给他们的邻居. Read the rest of this article »