标题可能不太清楚,但我会尽量在这里更好地解释:
- 假设我们有一个有向加权图G,有N个节点和K条边。
- 有两个主要节点:节点1和节点n。我们的主要目标是从1到n。通常从1到n有多条可能的路径。
- 我们也有M个人想从1到n。
- 每条边都有一个权值w,权值表示有多少人可以同时通过这条边。
- 每个边缘都可以想象成一条路,需要1天才能通过。
我们想要做的是让M个人从节点1到节点N,最小化所需天数。
例如:
图的例子
在这张图中,如果我们有3个人要经过,那么最少的天数是2天。我们将2个人传递给节点2,1个人传递给节点3。2个人2天到达节点3,1个人1天到达节点3。
我的问题是:如何解决这个问题?是用max-flow吗?如果是,如何对问题进行建模,以便用max-flow来解决?
- 正常应用最大流量算法
- 如果最大流量结果小于M
- 无解
- 如果最大流量结果等于M
- 如果最大流量结果大于M
- 按最远行程顺序从最大最大流量结果中移除人员,直到M离开。