网络流小结
联赛过后, 虽然遗憾的没拿到一等, 但这不是止步不前的时候, 于是我就学了学网络流, 学了这几天, 也该总结总结了......
网络流其实就是一种图论模型, 在这种图中, 边权变成了坑爹的流量, 常见的最短路问题也变成了最大流 - 最小割问题
网络图和普通图的最大区别也就是边权不再是一个干干巴巴的数字, 或者强赋意义的数量, 而是真真正正地变成了一个具有实际意义的量 - 容量. 我个人认为, 这在现实中有着更广泛的应用, 网络流量的分配, 水流量的分配等诸多问题, 都可以转化为这个模型, 网络流具有十分广泛的应用, 或许这也是它被称为图论的最高奥义的原因之一吧.
网络图的存储与普通的图并无太大不同, 这也得益于邻接表这一巧妙的设计, 我常用的存储方式是这样的:
- struct edge {
- int to , next , flow ; // 意义与普通邻接表相同, flow 就是 "边权", 也就是容量
- } ;
来源: http://www.bubuko.com/infodetail-3006704.html