目录
一个医院有n名医生，现有k个公共假期需要安排医生值班。每一个公共假期由若干天（假日）组成，第j个假期包含的假日用 Dj表示，那么需要排班的总假日集合为 
，如图1所示。例如，“五一”假期由5月1日至5月7日一共7个假日组成。“元旦”假期由1月1日至1月3日一共3个假日组成。
图1 问题示例
每名医生i可以值班的假日集合是 Si，Si⊆D。例如，李医生可以值班的假日集合包括“五一”假期中的5月3日、5月4日和“元旦”假期中的1月2日。
设计一个排班的方案使得每个假日都有一个医生值班并且满足下面两个条件：
根据上述场景完成下面任务：
我们首先具体化医生排班问题的参数，例如：假设一个医院有2名医生，现有国庆节和劳动节两个假期需要安排医生值班，假设两个假期假日都为2天。
A医生可以值班的假日为国庆假的第一天和第二天以及劳动节的第一天。B医生可以值班的假日为国庆假的第一天和劳动节的第二天。
设计一个排班的方案使得每个假日都有一个医生值班并且满足下面两个条件：
1. 每个医生最多只能值班2个假日；
2. 每个医生在一个假期中只能值班1个假日。
建立流网络
我们首先根据问题生成一个流网络，如图2所示，先创建一个超级源点S，让超级源点S到每个医生的流量都是2，即让每个医生至多值班2天；然后创建流网络的中间节点，并限制路径上的最大流量为1，即限制一个医生在一个假期中最多只值班一天；最后创建一个超级汇点T，让每个假日到超级汇点的流量都是1，即让每个假日都有一个医生值班。
图2 网络流的建立
然后给每个节点编号，上面的流网络等价于下面图3的流网络模型。若要得到满足问题的解，那么需要满足每个假日到超级汇点的流量都为1，即问题等价成要寻找该流网络中的一个最大流。
图3 流网络模型
Ford-Fulkerson方法是解决最大流问题的一种经典方法，包含几种运行时间的实现，其依赖于三种重要思想，即残存网络、增广路径和切割。
Ford-Fulkerson方法通过不断地在残留网络中搜索出增广路径，并根据增广路径更新剩余容量的方式来寻找最大流。每次增广的过程中，都会选择一条从源点到汇点的路径，然后将这条路径上的流量增加到当前的最大流中。随着可行流的不断增加，残留网络中的剩余容量也不断减少，直到找不到增广路径为止。
具体来说，首先根据流网络的最大流容量构建出残存网络，如图4所示。
图4 构建残存网络
接着搜索残存网络中的每一条增广路径，如图5所示，然后使用残存容量来对增广路径上的流进行加增，如果残存边是原来网络中的一条边，则加增流量，否则缩减流量。
图5 搜索增广路径更新网络流量
根据我们上面证明过的最大流最小割定理，f是G中的一个最大流当且仅当其对应的残存网络中不包含任何的增广路径，如图6所示，当残存网络中没有增广路径时，就已经找到了一个最大流。
图6 最大流
根据我们找到的最大流可知，与原流网络相比，结点3和结点7之间没有流通过，即A医生不值国庆节第一天的班，如图7所示，最后得出的方案是：A医生值国庆节的第二天班和劳动节的第一天班，B医生值国庆节的第一天班和劳动节的第二天班。
图7 医生排班方案
程序实现
定义一个Map 类表示一个有向图，使用一个二维数组记录每条边的容量，利用 DFS 不断寻找增广路径，从源点开始递归遍历未被访问过的相邻节点，如果当前节点是汇点则返回流量，否则继续递归寻找增广路径，返回从当前节点出发能够到达汇点的最大流量，同时更新相应的网络流。
C++代码
//
// Created by YEZI on 2023/6/20.
//
#ifndef MAX_FLOW_FORD_FULKERSON_H
#define MAX_FLOW_FORD_FULKERSON_H
#include<iostream>
#include<fstream>
using namespace std;
namespace Ford_Fulkerson {
class Map {
int **map;
bool *visited;
int edgeNumber;
int vertexNumber;
int max_flow = 0;
int sink;
int DFS(const int current, int min_flow) {
if (current == sink) {
return min_flow;
}
visited[current] = true;
for (int i = 0; i < vertexNumber; i++) {
if (map[current][i] && !visited[i]) {
int next_flow = DFS(i, min(map[current][i], min_flow));
if (next_flow) {
map[current][i] -= next_flow;
map[i][current] += next_flow;
return next_flow;
}
}
}
return 0;
}
public:
void find_max_flow() {
while (true) {
fill(visited, visited + vertexNumber, false);
int flow = DFS(0, 1314520);
if (flow == 0)
break;
max_flow += flow;
}
}
void show() {
cout << "Max flow is " << max_flow << endl;
for (int i = 0; i < vertexNumber; i++) {
for (int j = 0; j < vertexNumber; j++) {
if (map[i][j] && i < j)
cout << '<' << i << ',' << j << "> is abandoned." << endl;
}
}
}
Map(){
fstream file(R"(C:\Users\Yezi\Desktop\C++\max_flow\data.txt)");
if (!file.is_open()) {
cout << "File Open Error!" << endl;
return;
}
file >> vertexNumber >> edgeNumber;
map = new int *[vertexNumber];
visited = new bool[vertexNumber];
for (int i = 0; i < vertexNumber; i++) {
map[i] = new int[vertexNumber];
fill(map[i], map[i] + vertexNumber, 0);
}
sink = vertexNumber - 1;
int head, tail, capacity;
while (!file.eof()) {
file >> head >> tail >> capacity;
map[head][tail] = capacity;
}
}
Map(const int doctor_num,const int holiday_num,const int day_num,const int capacity) {
vertexNumber=1+doctor_num+doctor_num*holiday_num+holiday_num*day_num+1;
map = new int *[vertexNumber];
visited = new bool[vertexNumber];
for (int i = 0; i < vertexNumber; i++) {
map[i] = new int[vertexNumber];
fill(map[i], map[i] + vertexNumber, 0);
}
sink = vertexNumber - 1;
for(int doctor=1;doctor<=doctor_num;doctor++){
map[0][doctor]=capacity;
}
for(int doctor=1;doctor<=doctor_num;doctor++){
for(int holiday=0;holiday<holiday_num;holiday++){
int tail=1+doctor_num+doctor_num*holiday+doctor-1;
map[doctor][tail]=1;
int head=tail;
bool select[day_num];
fill(select,select+day_num,false);
for(int day=0;day<day_num/2+1;day++){
int index=rand()%day_num;
if(select[index]){
day--;
continue;
}
select[index]= true;
tail=1+doctor_num+doctor_num*holiday_num+day_num*holiday+index;
map[head][tail]=1;
}
}
}
for(int day=0;day<holiday_num*day_num;day++){
map[1+doctor_num+doctor_num*holiday_num+day][sink]=1;
}
}
};
}
#endif //MAX_FLOW_FORD_FULKERSON_H
用DFS实现的Ford-Fulkerson方法的运行结果如图8所示，找到最大流为4，结点3和结点7之间没有流通过，可以确认正确性。
图8 Ford-Fulkerson DFS实现运行结果
数据测试
固定假期数为20个，每个假期的天数为7天，一个医生最多可以值班10个假日，然后生成不同规模的医生数量进行测试，结果如图9所示。
图9 Ford-Fulkerson(DFS)测试
具体数据如表1所示。
表1 Ford-Fulkerson(DFS)测试
由结果可以看出，随着医生数量的增长，程序运行的时间呈线性增长。
Edmonds-karp算法是Ford-Fulkerson方法的一种实现，其主要思想是在残量网络上使用 BFS 查找增广路径，如图10所示，与我们上一个使用DFS实现不同，Edmonds-Karp 算法首先在残量网络上进行 BFS查找从源点到汇点的一条增广路径，然后根据增广路径更新流网络直到残存网络中没有增广路径为止。
图10 Edmonds-karp算法
C++代码
//
// Created by YEZI on 2023/6/20.
//
#ifndef MAX_FLOW_EDMONDS_KARP_H
#define MAX_FLOW_EDMONDS_KARP_H
#include<iostream>
#include<fstream>
#include<queue>
using namespace std;
namespace Edmonds_Karp {
class Map {
int **map;
int *pre;
int *flow;
int vertexNumber;
int edgeNumber;
int max_flow = 0;
int source;
int sink;
bool BFS() {
queue<int> q;
vector<bool> visited(vertexNumber, false);
flow[source] = INT_MAX;
visited[source] = true;
q.push(source);
while (!q.empty()) {
int current = q.front();
q.pop();
for (int i = 0; i < vertexNumber; i++) {
if (!visited[i] && map[current][i]) {
flow[i] = min(flow[current], map[current][i]);
pre[i] = current;
visited[i] = true;
if (i == sink)
return true;
q.push(i);
}
}
}
return false;
}
public:
void find_max_flow() {
while (BFS()) {
int f = flow[sink];
max_flow += f;
for (int i = sink; i != source; i = pre[i]) {
map[pre[i]][i] -= f;
map[i][pre[i]] += f;
}
}
}
void show() {
cout << "Max flow is " << max_flow << endl;
for (int i = 0; i < vertexNumber; i++) {
for (int j = 0; j < vertexNumber; j++) {
if (map[i][j] && i < j)
cout << '<' << i << ',' << j << "> is abandoned." << endl;
}
}
}
Map() {
fstream file(R"(C:\Users\Yezi\Desktop\C++\max_flow\data.txt)");
if (!file.is_open()) {
cout << "File Open Error!" << endl;
return;
}
file >> vertexNumber >> edgeNumber;
map = new int *[vertexNumber];
pre = new int[vertexNumber];
flow = new int[vertexNumber];
for (int i = 0; i < vertexNumber; i++) {
map[i] = new int[vertexNumber];
fill(map[i], map[i] + vertexNumber, 0);
}
int head, tail, capacity;
while (!file.eof()) {
file >> head >> tail >> capacity;
map[head][tail] = capacity;
}
source = 0;
sink = vertexNumber - 1;
}
Map(const int doctor_num,const int holiday_num,const int day_num,const int capacity) {
vertexNumber=1+doctor_num+doctor_num*holiday_num+holiday_num*day_num+1;
map = new int *[vertexNumber];
pre = new int[vertexNumber];
flow = new int[vertexNumber];
for (int i = 0; i < vertexNumber; i++) {
map[i] = new int[vertexNumber];
fill(map[i], map[i] + vertexNumber, 0);
}
sink = vertexNumber - 1;
source = 0;
for(int doctor=1;doctor<=doctor_num;doctor++){
map[0][doctor]=capacity;
}
for(int doctor=1;doctor<=doctor_num;doctor++){
for(int holiday=0;holiday<holiday_num;holiday++){
int tail=1+doctor_num+doctor_num*holiday+doctor-1;
map[doctor][tail]=1;
int head=tail;
bool select[day_num];
fill(select,select+day_num,false);
for(int day=0;day<day_num/2+1;day++){
int index=rand()%day_num;
if(select[index]){
day--;
continue;
}
select[index]= true;
tail=1+doctor_num+doctor_num*holiday_num+day_num*holiday+index;
map[head][tail]=1;
}
}
}
for(int day=0;day<holiday_num*day_num;day++){
map[1+doctor_num+doctor_num*holiday_num+day][sink]=1;
}
}
};
}
#endif //MAX_FLOW_EDMONDS_KARP_H
数据测试
首先使用我们图2的流网络进行测试验证算法的正确性，结果如图11所示，找到最大流为4，结点3和结点7之间没有流通过，说明算法正确，Edmonds-karp算法可以正确的解决医生排班问题。
图10 Edmonds-karp运行结果
固定假期数为20个，每个假期的天数为7天，一个医生最多可以值班10个假日，然后生成不同规模的医生数量进行测试，并与之前DFS实现的Ford-Fulkerson（简记为FF-DFS）方法做对比，结果如图11所示，Edmonds-karp简记为EK-BFS。
图11 Edmonds-karp测试
具体数据如表2所示。
表2 Edmonds-karp测试
由结果可知，与线性增长的DFS实现的Ford-Fulkerson方法不同，BFS实现的Edmonds-karp算法是随着医生数量的增长呈2次方式增长，BFS之所以慢于DFS是因为在医生排班问题中，流网络的层次固定为五层，DFS的效率不会低，而Edmonds-karp使用的BFS会随着医生数量的增长而搜索的宽度增加，因此更慢。
我们可以观察到，如图12所示，医生排班问题具有非常强的层次感，Dinic算法利用分层图的思想，在每一阶段搜索增广路径时只沿着分层图上深度逐渐加深的路径进行搜索。
图12 医生排班的强层次感
具体来说，Dinic算法首先使用BFS将所有节点分为不同的层级，然后使用DFS在深度逐渐加深的路径上进行搜索，如图13所示，每一条边只能跨越相邻层级之间的节点。每一次增广的路径新加的边都是从深层到浅层的，不会再次经过之前已经走过的边，从而减少重复计算。
图13 Dinic算法
C++代码
//
// Created by YEZI on 2023/6/20.
//
#ifndef MAX_FLOW_DINIC_H
#define MAX_FLOW_DINIC_H
#include<iostream>
#include<fstream>
#include<queue>
using namespace std;
namespace Dinic {
class Map {
int **map;
int *pre;
int *cur;
int *flow;
int *dis;
int vertexNumber;
int edgeNumber;
int max_flow = 0;
int source;
int sink;
bool BFS() {
queue<int> q;
fill(dis, dis + vertexNumber, -1);
flow[source] = INT_MAX;
dis[source] = 0;
q.push(source);
while (!q.empty()) {
int current = q.front();
q.pop();
for (int i = 0; i < vertexNumber; i++) {
if (dis[i] == -1 && map[current][i]) {
flow[i] = min(flow[current], map[current][i]);
pre[i] = current;
dis[i] = dis[current] + 1;
if (i == sink)
return true;
q.push(i);
}
}
}
return false;
}
int DFS(int u, int limit) {
if (u == sink || !limit)
return limit;
int totalFlow = 0;
for (int &i = cur[u]; i < vertexNumber; i++) {
if (dis[i] == dis[u] + 1 && map[u][i]) {
int d = DFS(i, min(limit, map[u][i]));
if (!d) {
dis[i] = -1;
} else {
limit -= d;
totalFlow += d;
map[u][i] -= d;
map[i][u] += d;
if (!limit)
break;
}
}
}
return totalFlow;
}
public:
void find_max_flow() {
while (BFS()) {
memcpy(cur, map[source], sizeof(int) * vertexNumber);
max_flow += DFS(source, INT_MAX);
}
}
void show() {
cout << "Max flow is " << max_flow << endl;
for (int i = 0; i < vertexNumber; i++) {
for (int j = 0; j < vertexNumber; j++) {
if (map[i][j] && i < j)
cout << '<' << i << ',' << j << "> is abandoned." << endl;
}
}
}
Map() {
fstream file(R"(C:\Users\Yezi\Desktop\C++\max_flow\data.txt)");
if (!file.is_open()) {
cout << "File Open Error!" << endl;
return;
}
file >> vertexNumber >> edgeNumber;
map = new int *[vertexNumber];
pre = new int[vertexNumber];
cur = new int[vertexNumber];
flow = new int[vertexNumber];
dis = new int[vertexNumber];
for (int i = 0; i < vertexNumber; i++) {
map[i] = new int[vertexNumber];
fill(map[i], map[i] + vertexNumber, 0);
}
int head, tail, capacity;
while (!file.eof()) {
file >> head >> tail >> capacity;
map[head][tail] = capacity;
}
source = 0;
sink = vertexNumber - 1;
}
Map(const int doctor_num,const int holiday_num,const int day_num,const int capacity) {
vertexNumber=1+doctor_num+doctor_num*holiday_num+holiday_num*day_num+1;
map = new int *[vertexNumber];
pre = new int[vertexNumber];
cur = new int[vertexNumber];
flow = new int[vertexNumber];
dis = new int[vertexNumber];
for (int i = 0; i < vertexNumber; i++) {
map[i] = new int[vertexNumber];
fill(map[i], map[i] + vertexNumber, 0);
}
sink = vertexNumber - 1;
source = 0;
for(int doctor=1;doctor<=doctor_num;doctor++){
map[0][doctor]=capacity;
}
for(int doctor=1;doctor<=doctor_num;doctor++){
for(int holiday=0;holiday<holiday_num;holiday++){
int tail=1+doctor_num+doctor_num*holiday+doctor-1;
map[doctor][tail]=1;
int head=tail;
bool select[day_num];
fill(select,select+day_num,false);
for(int day=0;day<day_num/2+1;day++){
int index=rand()%day_num;
if(select[index]){
day--;
continue;
}
select[index]= true;
tail=1+doctor_num+doctor_num*holiday_num+day_num*holiday+index;
map[head][tail]=1;
}
}
}
for(int day=0;day<holiday_num*day_num;day++){
map[1+doctor_num+doctor_num*holiday_num+day][sink]=1;
}
}
};
}
#endif //MAX_FLOW_DINIC_H
数据测试
首先使用我们图2的流网络进行测试验证算法的正确性，结果如图14所示，找到最大流为4，结点3和结点7之间没有流通过，说明算法正确，Dinic算法可以正确的解决医生排班问题。
图14 Dinic算法运行结果
固定假期数为20个，每个假期的天数为7天，一个医生最多可以值班10个假日，然后生成不同规模的医生数量进行测试，并与之前DFS实现的Ford-Fulkerson方法做对比，结果如图15所示。
图15 Dinic算法测试
具体数据如表3所示。
表3 Dinic算法测试
由结果可知，Dinic算法的执行效率要快于Edmonds-karp算法，理论上要快于DFS实现的Ford-Fulkerson算法，但是由于医生排班问题的流网络只有五层，DFS的效率仍然是非常高的。