NOI 2008 employee 招募一批志愿者，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。 一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。用尽量少的费用招募足够的志愿者.

Presentation on theme: "NOI 2008 employee 招募一批志愿者，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。 一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。用尽量少的费用招募足够的志愿者."— Presentation transcript:

1

2 NOI 2008 employee 招募一批志愿者，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。 一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。用尽量少的费用招募足够的志愿者

3 费 用 流 朱秋明 2015年8月

4 费用（代价） 容量 C 代价 b 注：反向边的代价为正向边的负数

5 1、 连续最短路算法（Successive Shortest Path）；
2、 消圈算法（Cycle Canceling）； 3、 原始对偶算法（Primal Dual）； 4、 网络单纯形（Network Simplex）。 （5、 ZKW算法）

6 连续最短路算法 SPFA

7 消圈法 消圈定理：残留网络里如果存在负费用圈，那么当前流不是最小费用流。 负圈：费用总和是负数，且每条边的剩余流量大于0

8 POJ 2175 有n座建筑物，每个建筑物里面有一些人，城市里面建了m座避难所。每座避难所只能容纳有限人数。
给出每个建筑物和避难所的坐标（曼哈顿距离+1）。现在给出一种避难方案，问这种方案是否为最优方案，如果不是，请输出一种比当前更优的方案（不一定最优）。

9 “请输出一种比当前更优的方案(不一定为最优)”
建图？ “请输出一种比当前更优的方案(不一定为最优)”

10 1、建立残留网 2、SPFA找负圈

11 [SCOI2007]修车 同一时刻有N位车主，维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。 （顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。）

12 建图： 1、将每个技术员分为N个点（第k个点表示修完前k+1辆后修第k辆）； 费用为：k * w(读入时间)；
2、加入顾客，分别与技术员连边，容量为1； 3、加入源点、汇点，跑最小费用流。

13 NOI 2008 employee 招募一批志愿者，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。 一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。用尽量少的费用招募足够的志愿者

14 种类 1 2 3 4 5 时间 1-2 1-1 2-3 3-3 3-4 费用 6 设雇佣第i类志愿者的人数为X[i] 每个志愿者的费用为V[i] 第j天雇佣的人数为P[j]

15 P[3] = X[3] + X[4] +X[5] >= 5 P[4] = X[5] >= 3
① P[1] - P[0] = X[1] + X[2] - Y[1] = 4 ② P[2] - P[1] = X[3] - X[2] -Y[2] +Y[1] = -2 ③ P[3] - P[2] = X[4] + X[5] - X[1] - Y[3] + Y[2] =3 ④ P[4] - P[3] = - X[3] - X[4] + Y[3] - Y[4] = -2 ⑤ P[5] - P[4] = - X[5] + Y[4] = -3

16

17

18 ① - X[1] - X[2] + Y[1] + 4 = 0 ② - X[3] + X[2] + Y[2] - Y[1] - 2 = 0 ③ - X[4] - X[5] + X[1] + Y[3] - Y[2] + 3 = 0 ④ X[3] + X[4] - Y[3] + Y[4] - 2 = 0 ⑤ X[5] - Y[4] - 3 = 0

19 网络流的精髓： 建模

20 谢谢！

21 Q&A