August 2017
Intermediate to advanced
360 pages
8h 35m
Chinese
Content preview from 算法技术手册（原书第2 版）
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
206
第
8
章
网络流算法
很多问题都可以抽象成包含顶点和边有容量限制的网络。本章从实际需求出发，介绍解
决这些特定类型问题的算法。
Ahuja
（
1993
）曾对大量网络流算法应用进行了深入的探讨：
任务分配
有一堆任务需要分配给员工完成。对于分配的任务，不同的员工所需要的费用不同。
现要求找到一种分配方式，使得总费用最小。
二分图匹配
有一些求职者需要面试一系列工作岗位，现要求找到一种合理的分配方式，使得尽
可能多的人找到他们能胜任的工作。
最大流
给定一个网络，网络中的每条边显示了两地之间潜在的货运量，现要求计算出这个
网络能够支持的最大流量。
运输问题
确定从工厂向零售商店运输商品性价比最高的方法。
转运问题
确定从工厂向到零售商店运输商品性价比最高的方法，但在这类问题中，我们可以
使用一些中转站作为临时仓库。
图
8-1
展示了将上述每个问题转换为网络流问题的过程，它们都是从一个或多个源顶点
流向到一个或多个汇点。关于问题最通用的定义见图的底部，图中描述的其他问题都是
对这一问题的改进。例如，运输问题就是转运问题的一个特例，因为运输图并不包含任
何的中转结点。因此，一个能够解决转运问题的程序肯定能够用于解决运输问题。
网络流算法
｜
207
网络流算法
图 8-1：网络流问题之间的关系
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.