devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【深圳大学算法设计与分析】实验六 最大流应用问题_深圳大学算法设计与分析实验六

作者：凡人多烦事01 | 2024-05-25 08:34:25

赞

踩

深圳大学算法设计与分析实验六

实验目的

（1）掌握最大流算法思想。

（2）学会用最大流算法求解应用问题。

实验内容与结果

为了完成实验，需要先了解几个算法：

（1）Ford-Fulkerson算法（FF算法）

Ford-Fulkerson算法是一种用于解决最大流问题的经典算法。最大流问题是在一个有向图中找到从源节点到汇节点的最大流量路径。

算法的基本思想是不断寻找增广路径，并通过增加路径上的流量来增加总体的流量。增广路径是指从源节点到汇节点的路径，其上的边的剩余容量大于零。通过不断寻找增广路径并增加流量，直到无法找到增广路径为止，就可以得到最大流。

Ford-Fulkerson算法的基本步骤如下：

1. 初始化流量为0。

2. 在图中找到一条增广路径。可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来寻找增广路径。

3. 如果存在增广路径，则确定路径上的最小剩余容量，这将成为增加的流量。

4. 在增广路径上更新每条边的流量，将流量增加到正向边上，减少流量到反向边上。

5. 重复步骤2-4，直到没有增广路径可以找到。

6. 最终，流量的总和就是最大流。

Ford-Fulkerson算法本身不提供最优解的保证。为了得到最大流的最优解，可以使用不同的方法来选择增广路径，如Edmonds-Karp算法，它使用广度优先搜索来选择增广路径，并保证在每次寻找增广路径时使用最短路径。

（2）Edmonds-Karp算法（EK算法）

Edmonds-Karp算法是一种基于Ford-Fulkerson算法的改进版本，用于解决最大流问题。与Ford-Fulkerson算法不同的是，Edmonds-Karp算法使用广度优先搜索（BFS）来选择增广路径，从而保证每次找到的增广路径是最短路径。

Edmonds-Karp算法的基本步骤如下：

1. 初始化流量为0。

2. 在图中使用广度优先搜索（BFS）找到一条增广路径。BFS会按照节点的层级顺序搜索，确保找到的路径是最短路径。

3. 如果存在增广路径，则确定路径上的最小剩余容量，这将成为增加的流量。

4. 在增广路径上更新每条边的流量，将流量增加到正向边上，减少流量到反向边上。

5. 重复步骤2-4，直到没有增广路径可以找到。

6. 最终，流量的总和就是最大流。

通过使用广度优先搜索来选择最短增广路径，Edmonds-Karp算法保证了每次迭代增加的流量是最优的。算法的时间复杂度为O(V * E2)，其中V是节点数，E是边数。

Edmonds-Karp算法的优点是可以得到最大流的最优解，而不仅仅是一个可行解。此外，由于使用了广度优先搜索，它的运行时间相对较短，适用于中等规模的问题。

综上所述，Edmonds-Karp算法是一种基于广度优先搜索的改进版Ford-Fulkerson算法，用于解决最大流问题，通过保证每次找到的增广路径是最短路径来获得最优解。

EK算法核心部分伪代码如下

（3）Dinic算法

Dinic算法是一种用于解决最大流问题的高效算法。它基于增广路径的概念，并使用了一种称为层次图的数据结构来加速查找增广路径的过程。

Dinic算法的基本步骤如下：

1. 构建初始的残余网络，其中所有边的初始流量为0。

2. 构建层次图，即通过广度优先搜索（BFS）确定每个节点的层级，从源节点开始，每一层只包含从前一层到达的节点。

3. 当存在层次图中的增广路径时，执行以下步骤：

   a. 在层次图中使用深度优先搜索（DFS）查找增广路径，路径上的边必须满足残余容量大于0。

   b. 在DFS过程中，尽量选择残余容量最大的边，以加快算法的收敛速度。

   c. 如果找到增广路径，则确定路径上的最小残余容量，这将成为增加的流量。

   d. 在增广路径上更新每条边的流量，增加流量到正向边上，减少流量到反向边上。

   e. 更新残余网络，即更新每条边的残余容量。

   f. 重复步骤3直到没有增广路径可以找到。

4. 最终，流量的总和就是最大流。

Dinic算法的主要优势在于它的高效性。在每次迭代中，Dinic算法可以找到多条增广路径，并且在每次迭代中，层次图的层级结构都会保持不变，因此可以避免重复计算。算法的时间复杂度为O(V2 * E)，其中V是节点数，E是边数，这使得Dinic算法在大多数实际情况下具有较好的性能。

Danic算法核心部分伪代码如下

Danic算法相较EK算法的优势

1. 时间复杂度更优：Dinic算法的时间复杂度为O(V2 * E)，而Edmonds-Karp算法的时间复杂度为O(V * E2)。在稠密图（边数接近顶点数的平方）中，Dinic算法通常比Edmonds-Karp算法更快。这是因为Dinic算法通过使用层次图和BFS构造增广路径，减少了不必要的搜索和迭代次数。

2. 增广路径选择更优：Dinic算法在每次迭代中选择残余容量最大的边作为增广路径的一部分，从而在每次迭代中增加更多的流量。这使得Dinic算法收敛更快，可以找到更快的最大流。

3. 不会出现返流：Edmonds-Karp算法在每次迭代时使用BFS选择增广路径，可能会导致在残余图中出现返流边，从而需要对返流边进行反复的搜索和调整。而Dinic算法使用层次图构建增广路径，保证了每次迭代中不会出现返流边，从而减少了不必要的操作。

4. 空间效率更高：Dinic算法使用层次图作为辅助数据结构，而不需要维护整个残余图。这使得Dinic算法的空间复杂度较低，只需O(V)的额外空间。

综上所述，Dinic算法相比于Edmonds-Karp算法在时间复杂度、增广路径选择、返流处理和空间效率等方面具有优势。它能够更快地找到最大流，并且在大多数实际情况下表现更优。

因此，接下来使用Danic算法完成实验。

简化题目：

一个医院有 n 名医生，现有 k 个公共假期，每一个公共假期有q天。例如，“五一”假期由5月1日至5月7日一共7天。“元旦”假期由1月1日至1月3日一共3天。

每名医生均有一个可值班的假日集合。例如，李医生可以值班的假日集合包括“五一”假期中的5月3日、5月4日，和“元旦”假期中的1月2日。

每个医生总共最多值班c天。

每个医生在一个假期中只能值班1天。例如，安排李医生在某个假期的某天值班后，那么便不能安排李医生在该假期的其它天值班。

根据上述场景完成下面任务：

（1）生成数据有n名医生，k个假期，每个假期有q天，每个医生总共最多值班c天，每个医生在一个假期中只能值班1天。

（2）用Danic算法求解上述问题，基于生成的数据，设计一个流网络；并计算出排班的方案。

可以设计如下图所示的流网络，源点连接医生，每个医生再连接可值班的假期，假期再连接可值班的假日，最后找到的有流量的的边即为分配方案。

步骤如下：

1. 创建节点：

   - 源点（Source）：表示医生的起始节点。

   - 医生节点：表示每个医生，例如医生n1、n2、n3。

   - 假期节点：表示每个假期，例如假期k1、k2。

   - 假日节点：表示每个假期的每一天，例如假期k1的第一天、第二天、第三天，假期k2的第一天、第二天、第三天。

   - 汇点（Sink）：表示流网络的终点。

2. 添加边和容量：

   - 源点到医生节点：将容量设置为每个医生可值班的最大天数c。

   - 医生节点到假期节点：将容量设置为1，表示医生只能在一个假期中值班一天。

   - 假期节点到假日节点：将容量设置为1，表示每个假期的每一天只能安排一个医生值班。

   - 假日节点到汇点：将容量设置为1，表示每一天只能安排一个医生值班。

3. 运行Dinic算法：

   - 使用Dinic算法计算最大流量，从源点流向汇点的最大流量即表示可安排的最大值班天数。

   - 根据最大流量的结果，确定每个医生在哪些假期的哪些假日值班。

运行后结果如下

数据统计如下

绘折线图如下

可以看出随着数据规模增大，耗时也会逐渐增大。

但因为采用了Danic算法优化，因此数据规模增大后，耗时仍在在ms级内，属于可以接受的范围。

实验总结

通过本次实验，加深了对最大流算法的理解和运用，加深了流网络、割、增广路径、残留网络、残留容量等概念的理解。理解了Ford-Fulkerson算法、EDMONDS-KARP算法、Dinic算法。

实验伪代码

  1. //EK算法 
  2. function EdmondsKarpAlgorithm(graph, source, sink):
  3.     // 初始化残余图，将所有边的流量设为0
  4.     residualGraph = InitializeResidualGraph(graph)
  5.  
  6.     // 初始化最大流量为0
  7.     maxFlow = 0
  8.  
  9.     // 在残余图中存在增广路径时继续循环
  10.     while ThereExistsAugmentingPath(residualGraph, source, sink):
  11.         // 使用广度优先搜索（BFS）找到一条增广路径
  12.         augmentingPath = FindAugmentingPath(residualGraph, source, sink)
  13.  
  14.         // 找到增广路径后，计算路径上的最小残余容量
  15.         minCapacity = FindMinCapacity(augmentingPath)
  16.  
  17.         // 在增广路径上更新每条边的流量
  18.         UpdateFlow(residualGraph, augmentingPath, minCapacity)
  19.  
  20.         // 更新最大流量
  21.         maxFlow = maxFlow + minCapacity
  22.  
  23.     // 返回最大流量
  24.     return maxFlow
  25.     
  26. function InitializeResidualGraph(graph):
  27.     residualGraph = createEmptyGraph()
  28.  
  29.     // 在残余图中复制原始图的边，并将初始流量设为0
  30.     for each edge (u, v) in graph:
  31.         residualGraph.addEdge(u, v, capacity=graph[u][v], flow=0)
  32.  
  33.     return residualGraph
  34.  
  35. function ThereExistsAugmentingPath(residualGraph, source, sink):
  36.     // 使用广度优先搜索（BFS）查找从源节点到汇节点的增广路径
  37.     visited = createEmptySet()
  38.     queue = createEmptyQueue()
  39.     queue.enqueue(source)
  40.     visited.add(source)
  41.  
  42.     while queue is not empty:
  43.         currentVertex = queue.dequeue()
  44.  
  45.         // 遍历当前节点的邻居节点
  46.         for each neighbor in residualGraph.getNeighbors(currentVertex):
  47.             // 如果邻居节点未被访问且残余容量大于0，则加入队列并标记为已访问
  48.             if neighbor not in visited and residualGraph.getResidualCapacity(currentVertex, neighbor) > 0:
  49.                 queue.enqueue(neighbor)
  50.                 visited.add(neighbor)
  51.                 // 记录从源节点到当前节点的路径
  52.                 residualGraph.setParent(neighbor, currentVertex)
  53.  
  54.     // 如果汇节点被访问到了，说明存在增广路径
  55.     return sink in visited
  56.  
  57. function FindAugmentingPath(residualGraph, source, sink):
  58.     // 使用深度优先搜索（DFS）找到从源节点到汇节点的增广路径
  59.     path = []
  60.     currentVertex = sink
  61.  
  62.     while currentVertex != source:
  63.         // 将当前节点添加到路径中
  64.         path.append(currentVertex)
  65.         // 获取当前节点的父节点
  66.         parent = residualGraph.getParent(currentVertex)
  67.         // 在残余图中删除当前节点和父节点之间的边，相当于将其标记为已访问
  68.         residualGraph.removeEdge(parent, currentVertex)
  69.         currentVertex = parent
  70.  
  71.     // 将源节点添加到路径中
  72.     path.append(source)
  73.     // 反转路径，使其从源节点到汇节点
  74.     path.reverse()
  75.  
  76.     // 返回增广路径
  77.     return path
  78.  
  79. function FindMinCapacity(augmentingPath):
  80.     // 初始化最小残余容量为正无穷
  81.     minCapacity = infinity
  82.  
  83.     // 遍历增广路径上的边，找到最小的残余容量
  84.     for each edge (u, v) in augmentingPath:
  85.         // 获取当前边的残余容量
  86.         residualCapacity = residualGraph.getResidualCapacity(u, v)
  87.         // 更新最小残余容量
  88.         minCapacity = min(minCapacity, residualCapacity)
  89.  
  90.     // 返回最小残余容量
  91.     return minCapacity
  92.  
  93. function UpdateFlow(residualGraph, augmentingPath, minCapacity):
  94.     // 在增广路径上更新每条边的流量
  95.     for each edge (u, v) in augmentingPath:
  96.         // 增加流量到正向边上
  97.         residualGraph.increaseFlow(u, v, minCapacity)
  98.         // 减少流量到反向边上
  99.         residualGraph.decreaseFlow(v, u, minCapacity)
  100.  
  101.  
  102.  
  103. //Danic算法
  104. function DinicAlgorithm(graph, source, sink):
  105.     // 构建初始的残余网络，将所有边的初始流量设为0
  106.     residualGraph = InitializeResidualGraph(graph)
  107.  
  108.     // 初始化最大流量为0
  109.     maxFlow = 0
  110.  
  111.     // 构建层次图（Layered Graph），即确定每个节点的层级
  112.     while ConstructLayeredGraph(residualGraph, source, sink):
  113.         // 在层次图中存在增广路径时继续循环
  114.         while true:
  115.             // 使用深度优先搜索（DFS）查找增广路径
  116.             augmentingPath = FindAugmentingPath(residualGraph, source, sink)
  117.  
  118.             // 如果没有找到增广路径，跳出内层循环
  119.             if augmentingPath is None:
  120.                 break
  121.  
  122.             // 计算路径上的最小残余容量
  123.             minCapacity = FindMinCapacity(augmentingPath)
  124.  
  125.             // 在增广路径上更新每条边的流量
  126.             UpdateFlow(residualGraph, augmentingPath, minCapacity)
  127.  
  128.             // 更新最大流量
  129.             maxFlow = maxFlow + minCapacity
  130.  
  131.     // 返回最大流量
  132.     return maxFlow
  133.     
  134. function InitializeResidualGraph(graph):
  135.     residualGraph = createEmptyGraph()
  136.  
  137.     // 在残余图中复制原始图的边，并将初始流量设为0 
  138.     for each edge (u, v) in graph:
  139.         residualGraph.addEdge(u, v, capacity=graph[u][v], flow=0)
  140.  
  141.     return residualGraph
  142.     
  143. function ConstructLayeredGraph(residualGraph, source, sink):
  144.     // 使用广度优先搜索（BFS）构建层次图
  145.     residualGraph.resetLevels()
  146.     residualGraph.setLevel(source, 0)
  147.  
  148.     queue = createEmptyQueue()
  149.     queue.enqueue(source)
  150.  
  151.     while queue is not empty:
  152.         currentVertex = queue.dequeue()
  153.  
  154.         // 遍历当前节点的邻居节点
  155.         for each neighbor in residualGraph.getNeighbors(currentVertex):
  156.             // 如果邻居节点未被标记层级且残余容量大于0，则将其标记为下一层级
  157.             if residualGraph.getLevel(neighbor) == -1 and residualGraph.getResidualCapacity(currentVertex, neighbor) > 0:
  158.                 residualGraph.setLevel(neighbor, residualGraph.getLevel(currentVertex) + 1)
  159.                 queue.enqueue(neighbor)
  160.  
  161.     // 如果汇节点被标记层级，说明层次图构建完成
  162.     return residualGraph.getLevel(sink) != -1
  163.  
  164. function FindAugmentingPath(residualGraph, currentVertex, sink, minCapacity):
  165.     // 如果当前节点等于汇节点，返回增广路径
  166.     if currentVertex == sink:
  167.         return [sink]
  168.  
  169.     // 遍历当前节点的邻居节点
  170.     for each neighbor in residualGraph.getNeighbors(currentVertex):
  171.         // 如果邻居节点的层级是当前节点的下一层级且残余容量大于0
  172.         if residualGraph.getLevel(neighbor) == residualGraph.getLevel(currentVertex) + 1 and residualGraph.getResidualCapacity(currentVertex, neighbor) > 0:
  173.             // 递归地查找从邻居节点到汇节点的增广路径
  174.             augmentingPath = FindAugmentingPath(residualGraph, neighbor, sink, min(minCapacity, residualGraph.getResidualCapacity(currentVertex, neighbor)))
  175.  
  176.             // 如果找到增广路径，将当前节点添加到路径中并返回路径
  177.             if augmentingPath is not None:
  178.                 augmentingPath.append(currentVertex)
  179.                 return augmentingPath
  180.  
  181.     // 如果没有找到增广路径，返回空
  182.     return None
  183.  
  184. function FindMinCapacity(augmentingPath):
  185.     // 初始化最小残余容量为正无穷
  186.     minCapacity = infinity
  187.  
  188.     // 遍历增广路径上的边，找到最小的残余容量
  189.     for each edge (u, v) in augmentingPath:
  190.         // 获取当前边的残余容量
  191.         residualCapacity = residualGraph.getResidualCapacity(u, v)
  192.         // 更新最小残余容量
  193.         minCapacity = min(minCapacity, residualCapacity)
  194.  
  195.     // 返回最小残余容量
  196.     return minCapacity
  197.  
  198. function UpdateFlow(residualGraph, augmentingPath, minCapacity):
  199.     // 在增广路径上更新每条边的流量
  200.     for each edge (u, v) in augmentingPath:
  201.         // 增加流量到正向边上
  202.         residualGraph.increaseFlow(u, v, minCapacity)
  203.         // 减少流量到反向边上
  204.         residualGraph.decreaseFlow(v, u, minCapacity)
  205.

实验代码

first.cpp

  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <limits>
  5. #include <queue>
  6. #include <cstdlib>
  7. #include <ctime>
  8. #include <unordered_set>
  9. using namespace std;
  10.  
  11. // 生成指定范围内的随机整数
  12. int getRandomNumber(int minVal, int maxVal) {
  13.     return minVal + rand() % (maxVal - minVal + 1);
  14. }
  15.  
  16. // 随机生成医生的假日集合
  17. unordered_set<int> generateDoctorHolidays(int numHolidays, int numDays) {
  18.     unordered_set<int> holidays;
  19.     while (holidays.size() < numDays) {
  20.         int holiday = getRandomNumber(1, numHolidays * numDays);
  21.         holidays.insert(holiday);
  22.     }
  23.     return holidays;
  24. }
  25.  
  26. // 边的数据结构
  27. struct Edge {
  28.     int from;
  29.     int to;
  30.     int capacity;
  31.     int flow;
  32.  
  33.     Edge(int from, int to, int capacity, int flow) : from(from), to(to), capacity(capacity), flow(flow) {}
  34. };
  35.  
  36. // Dinic算法的实现
  37. class DinicAlgorithm {
  38. public:
  39.     DinicAlgorithm(int numNodes) : numNodes(numNodes) {
  40.         adjList.resize(numNodes);
  41.         level.resize(numNodes);
  42.         nextEdgeIndex.resize(numNodes);
  43.     }
  44.  
  45.     void addEdge(int from, int to, int capacity) {
  46.         adjList[from].push_back(edges.size());
  47.         edges.push_back(Edge(from, to, capacity, 0));
  48.         adjList[to].push_back(edges.size());
  49.         edges.push_back(Edge(to, from, 0, 0));
  50.     }
  51.  
  52.     bool bfs(int source, int sink) {
  53.         fill(level.begin(), level.end(), -1);
  54.         level[source] = 0;
  55.  
  56.         queue<int> q;
  57.         q.push(source);
  58.  
  59.         while (!q.empty()) {
  60.             int current = q.front();
  61.             q.pop();
  62.  
  63.             for (int edgeIndex : adjList[current]) {
  64.                 Edge& edge = edges[edgeIndex];
  65.                 if (level[edge.to] == -1 && edge.capacity > edge.flow) {
  66.                     level[edge.to] = level[current] + 1;
  67.                     q.push(edge.to);
  68.                 }
  69.             }
  70.         }
  71.  
  72.         return level[sink] != -1;
  73.     }
  74.  
  75.     int dfs(int current, int sink, int minCapacity) {
  76.         if (current == sink) {
  77.             return minCapacity;
  78.         }
  79.  
  80.         while (nextEdgeIndex[current] < adjList[current].size()) {
  81.             int edgeIndex = adjList[current][nextEdgeIndex[current]];
  82.             Edge& edge = edges[edgeIndex];
  83.  
  84.             if (level[edge.to] == level[current] + 1 && edge.capacity > edge.flow) {
  85.                 int bottleneckCapacity = dfs(edge.to, sink, min(minCapacity, edge.capacity - edge.flow));
  86.                 if (bottleneckCapacity > 0) {
  87.                     edge.flow += bottleneckCapacity;
  88.                     edges[edgeIndex ^ 1].flow -= bottleneckCapacity;
  89.                     return bottleneckCapacity;
  90.                 }
  91.             }
  92.  
  93.             nextEdgeIndex[current]++;
  94.         }
  95.  
  96.         return 0;
  97.     }
  98.  
  99.     int maxFlow(int source, int sink) {
  100.         int totalFlow = 0;
  101.         while (bfs(source, sink)) {
  102.             fill(nextEdgeIndex.begin(), nextEdgeIndex.end(), 0);
  103.             int flow;
  104.             while ((flow = dfs(source, sink, numeric_limits<int>::max())) > 0) {
  105.                 totalFlow += flow;
  106.             }
  107.         }
  108.         return totalFlow;
  109.     }
  110.  
  111. //private:
  112.     int numNodes;
  113.     vector<Edge> edges;
  114.     vector<vector<int>> adjList;
  115.     vector<int> level;
  116.     vector<int> nextEdgeIndex;
  117. };
  118.  
  119. // 主函数
  120. int main()
  121. {
  122.     int numDoctors = 3;
  123.     int numHolidays = 2;
  124.     int numDays = 3;
  125.     int maxDutyDays = 3;
  126.  
  127.     DinicAlgorithm dinic(numDoctors + numHolidays * numDays + 2); // 加2是为了添加源点和汇点
  128.  
  129.     int source = 0;
  130.     int sink = numDoctors + numHolidays * numDays + 1;
  131.  
  132.     // 构建网络图
  133.     for (int i = 1; i <= numDoctors; i++) {
  134.         dinic.addEdge(source, i, maxDutyDays); // 源点到医生的边，容量为每名医生最多值班的天数
  135.     }
  136.  
  137.     for (int i = 1; i <= numHolidays; i++) {
  138.         for (int j = 1; j <= numDays; j++) {
  139.             int holidayNode = numDoctors + (i - 1) * numDays + j;
  140.             dinic.addEdge(holidayNode, sink, 1); // 假日到汇点的边，容量为1
  141.  
  142.             // 医生到假日的边，容量为1，根据医生的可值班假日集合确定边的连接关系
  143.             // 医生n1的假日集合：{k1的第二天和第三天、k2的第二天和第三天}
  144.             if (i == 1 && (j == 2 || j == 3)) {
  145.                 dinic.addEdge(1, holidayNode, 1);
  146.             }
  147.             // 医生n2的假日集合：{k1的第一天和第二天、k2的第一天和第二天}
  148.             if (i == 1 && (j == 1 || j == 2)) {
  149.                 dinic.addEdge(2, holidayNode, 1);
  150.             }
  151.             // 医生n3的假日集合：{k1的第二天和第三天、k2的第一天和第二天}
  152.             if ((i == 1 && (j == 2 || j == 3)) || (i == 2 && (j == 1 || j == 2))) {
  153.                 dinic.addEdge(3, holidayNode, 1);
  154.             }
  155.         }
  156.     }
  157.  
  158.     // 求解最大流量
  159.     int maxFlow = dinic.maxFlow(source, sink);
  160.  
  161.     cout << "Max flow: " << maxFlow << endl;
  162.  
  163.     // 输出分配方案
  164.     for (int i = 0; i < dinic.adjList.size(); i++) {
  165.         for (int edgeIndex : dinic.adjList[i]) {
  166.             Edge& edge = dinic.edges[edgeIndex];
  167.             if (edge.from != source && edge.to != sink && edge.flow > 0) {
  168.                 cout << "Doctor " << edge.from << " assigned to Holiday " << (edge.to - numDoctors - 1) / numDays + 1
  169.                     << ", Day " << (edge.to - numDoctors - 1) % numDays + 1 << endl;
  170.             }
  171.         }
  172.     }
  173.  
  174.     return 0;
  175. }
  176.

 

medium.cpp

  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdlib>
  4. #include <ctime>
  5. #include <unordered_set>
  6. #include <queue>
  7. #include <algorithm>
  8. #include <unordered_map>
  9. #include<sstream>
  10.  
  11. using namespace std;
  12.  
  13. // Dinic算法中的边数据结构
  14. struct Edge {
  15.     int from;
  16.     int to;
  17.     int capacity;
  18.     int flow;
  19.  
  20.     Edge(int from, int to, int capacity) : from(from), to(to), capacity(capacity), flow(0) {}
  21. };
  22.  
  23. // Dinic算法中的流网络数据结构
  24. class Dinic {
  25. public:
  26.     int numNodes;
  27.     vector<vector<int>> adjList;
  28.     vector<Edge> edges;
  29.     vector<int> level;
  30.     vector<int> nextEdgeIndex;
  31.  
  32.     Dinic(int numNodes) : numNodes(numNodes), adjList(numNodes), level(numNodes), nextEdgeIndex(numNodes) {}
  33.  
  34.     void addEdge(int from, int to, int capacity) {
  35.         adjList[from].push_back(edges.size());
  36.         edges.emplace_back(from, to, capacity);
  37.         adjList[to].push_back(edges.size());
  38.         edges.emplace_back(to, from, 0);
  39.     }
  40.  
  41.     bool bfs(int source, int sink) {
  42.         fill(level.begin(), level.end(), -1);
  43.         level[source] = 0;
  44.  
  45.         queue<int> q;
  46.         q.push(source);
  47.  
  48.         while (!q.empty()) {
  49.             int currentNode = q.front();
  50.             q.pop();
  51.  
  52.             for (int edgeIndex : adjList[currentNode]) {
  53.                 Edge& edge = edges[edgeIndex];
  54.                 if (level[edge.to] == -1 && edge.capacity > edge.flow) {
  55.                     level[edge.to] = level[currentNode] + 1;
  56.                     q.push(edge.to);
  57.                 }
  58.             }
  59.         }
  60.  
  61.         return level[sink] != -1;
  62.     }
  63.  
  64.     int dfs(int currentNode, int minCapacity, int sink) {
  65.         if (currentNode == sink)
  66.             return minCapacity;
  67.  
  68.         for (int& edgeIndex = nextEdgeIndex[currentNode]; edgeIndex < adjList[currentNode].size(); edgeIndex++) {
  69.             Edge& edge = edges[adjList[currentNode][edgeIndex]];
  70.             if (level[edge.to] == level[currentNode] + 1 && edge.capacity > edge.flow) {
  71.                 int bottleneck = dfs(edge.to, min(minCapacity, edge.capacity - edge.flow), sink);
  72.                 if (bottleneck > 0) {
  73.                     edge.flow += bottleneck;
  74.                     edges[adjList[currentNode][edgeIndex] ^ 1].flow -= bottleneck;
  75.                     return bottleneck;
  76.                 }
  77.             }
  78.         }
  79.  
  80.         return 0;
  81.     }
  82.  
  83.     int maxFlow(int source, int sink) {
  84.         int maxFlow = 0;
  85.         while (bfs(source, sink)) {
  86.             fill(nextEdgeIndex.begin(), nextEdgeIndex.end(), 0);
  87.             int bottleneck;
  88.             while ((bottleneck = dfs(source, INT_MAX, sink)) > 0) {
  89.                 maxFlow += bottleneck;
  90.             }
  91.         }
  92.         return maxFlow;
  93.     }
  94. };
  95.  
  96. // 生成指定范围内的随机整数
  97. int getRandomNumber(int minVal, int maxVal) {
  98.     return minVal + rand() % (maxVal - minVal + 1);
  99. }
  100.  
  101. // 随机生成医生的假日集合
  102. unordered_set<int> generateDoctorHolidays(int numHolidays, int numDays) {
  103.     unordered_set<int> holidays;
  104.     while (holidays.size() < numDays) {
  105.         int holiday = getRandomNumber(1, numHolidays * numDays);
  106.         holidays.insert(holiday);
  107.     }
  108.     return holidays;
  109. }
  110.  
  111. // 将假日的编号转换为具体的日期
  112. string getHolidayDate(int holiday, int numDaysPerMonth) {
  113.     int month = (holiday - 1) / numDaysPerMonth + 1;
  114.     int day = (holiday - 1) % numDaysPerMonth + 1;
  115.     return to_string(month) + "/" + to_string(day);
  116. }
  117.  
  118. // 输出医生的排班方案
  119. void printSchedule(const vector<unordered_map<int, string>>& schedule, int numDaysPerMonth) {
  120.     for (int i = 0; i < schedule.size(); i++) {
  121.         cout << "Doctor " << i + 1 << " schedule: ";
  122.         for (const auto& entry : schedule[i]) {
  123.             //cout << getHolidayDate(entry.first, numDaysPerMonth) << " - " << entry.second << "  ";
  124.             cout << getHolidayDate(entry.first, numDaysPerMonth) << " - " << entry.second << "  ";
  125.         }
  126.         cout << endl;
  127.     }
  128. }
  129.  
  130. int main() {
  131.     srand(static_cast<unsigned>(time(0))); // 设置随机数种子
  132.  
  133.     int numDoctors; // 医生数量
  134.     int numHolidays; // 假期数量
  135.     int numDays; // 每个假期的天数
  136.     int maxDutyDays; // 每名医生最多值班的天数
  137.  
  138.     cout << "Enter the number of doctors: ";
  139.     cin >> numDoctors;
  140.  
  141.     cout << "Enter the number of holidays: ";
  142.     cin >> numHolidays;
  143.  
  144.     cout << "Enter the number of days per holiday: ";
  145.     cin >> numDays;
  146.  
  147.     cout << "Enter the maximum duty days per doctor: ";
  148.     cin >> maxDutyDays;
  149.  
  150.     // 生成每个医生的假日集合
  151.     vector<unordered_set<int>> doctorHolidays(numDoctors);
  152.     for (int i = 0; i < numDoctors; i++) {
  153.         doctorHolidays[i] = generateDoctorHolidays(numHolidays, numDays);
  154.     }
  155.  
  156.     // 输出生成的数据
  157.     cout << "Number of doctors: " << numDoctors << endl;
  158.     cout << "Number of holidays: " << numHolidays << endl;
  159.     cout << "Number of days per holiday: " << numDays << endl;
  160.     cout << "Maximum duty days per doctor: " << maxDutyDays << endl;
  161.     for (int i = 0; i < numDoctors; i++) {
  162.         cout << "Doctor " << i + 1 << " holidays: ";
  163.         for (int holiday : doctorHolidays[i]) {
  164.             cout << holiday << " ";
  165.         }
  166.         cout << endl;
  167.     }
  168.  
  169.     // 构建流网络
  170.     int numNodes = numDoctors + numHolidays * numDays + 2; // 医生节点 + 假期节点 + 源点 + 汇点
  171.     int source = 0;
  172.     int sink = numNodes - 1;
  173.     Dinic dinic(numNodes);
  174.  
  175.     // 添加医生节点和源点之间的边
  176.     for (int i = 1; i <= numDoctors; i++) {
  177.         dinic.addEdge(source, i, maxDutyDays);
  178.     }
  179.  
  180.     // 添加假期节点和汇点之间的边
  181.     int nodeOffset = numDoctors;
  182.     // 添加假期节点和汇点之间的边
  183.         for (int i = 1; i <= numHolidays; i++) {
  184.             for (int j = 1; j <= numDays; j++) {
  185.                 dinic.addEdge(nodeOffset + (i - 1) * numDays + j, sink, 1);
  186.             }
  187.         }
  188.  
  189.     // 添加医生节点和假期节点之间的边
  190.     for (int i = 1; i <= numDoctors; i++) {
  191.         for (int j = 1; j <= numHolidays; j++) {
  192.             for (int k = 1; k <= numDays; k++) {
  193.                 if (doctorHolidays[i - 1].count((j - 1) * numDays + k) > 0) {
  194.                     dinic.addEdge(i, nodeOffset + (j - 1) * numDays + k, 1);
  195.                 }
  196.             }
  197.         }
  198.     }
  199.  
  200.     int qi, zhi;
  201.     qi = clock();
  202.     // 使用Dinic算法求解最大流
  203.     int maxFlow = dinic.maxFlow(source, sink);
  204.  
  205.     cout << "Maximum flow: " << maxFlow << endl;
  206.  
  207.     // 解析最大流，生成医生的排班方案
  208.     vector<unordered_map<int, string>> schedule(numDoctors);
  209.     for (const auto& edge : dinic.edges) {
  210.         if (edge.from >= 1 && edge.from <= numDoctors && edge.to >= nodeOffset + 1) {
  211.             if (edge.flow > 0) {
  212.                 int doctor = edge.from;
  213.                 int holiday = (edge.to - nodeOffset - 1) / numDays + 1;
  214.                 string date = getHolidayDate(edge.to - nodeOffset, numDays);
  215.                 schedule[doctor - 1][holiday] = date;
  216.             }
  217.         }
  218.     }
  219.     zhi = clock();
  220.  
  221.     // 输出医生的排班方案
  222.     //printSchedule(schedule, numDays);
  223.     cout << "耗时：" << zhi - qi << " ms" << endl;
  224.  
  225.     return 0;
  226. }

 

final.cpp

  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdlib>
  4. #include <ctime>
  5. #include <unordered_set>
  6. #include <queue>
  7. #include <algorithm>
  8. #include <unordered_map>
  9. #include<sstream>
  10. #include <chrono>
  11. using namespace std;
  12. using namespace std::chrono;
  13.  
  14. // Dinic算法中的边数据结构
  15. struct Edge {
  16.     int from;
  17.     int to;
  18.     int capacity;
  19.     int flow;
  20.  
  21.     Edge(int from, int to, int capacity) : from(from), to(to), capacity(capacity), flow(0) {}
  22. };
  23.  
  24. // Dinic算法中的流网络数据结构
  25. class Dinic {
  26. public:
  27.     int numNodes;
  28.     vector<vector<int>> adjList;
  29.     vector<Edge> edges;
  30.     vector<int> level;
  31.     vector<int> nextEdgeIndex;
  32.  
  33.     Dinic(int numNodes) : numNodes(numNodes), adjList(numNodes), level(numNodes), nextEdgeIndex(numNodes) {}
  34.  
  35.     void addEdge(int from, int to, int capacity) {
  36.         adjList[from].push_back(edges.size());
  37.         edges.emplace_back(from, to, capacity);
  38.         adjList[to].push_back(edges.size());
  39.         edges.emplace_back(to, from, 0);
  40.     }
  41.  
  42.     bool bfs(int source, int sink) {
  43.         fill(level.begin(), level.end(), -1);
  44.         level[source] = 0;
  45.  
  46.         queue<int> q;
  47.         q.push(source);
  48.  
  49.         while (!q.empty()) {
  50.             int currentNode = q.front();
  51.             q.pop();
  52.  
  53.             for (int edgeIndex : adjList[currentNode]) {
  54.                 Edge& edge = edges[edgeIndex];
  55.                 if (level[edge.to] == -1 && edge.capacity > edge.flow) {
  56.                     level[edge.to] = level[currentNode] + 1;
  57.                     q.push(edge.to);
  58.                 }
  59.             }
  60.         }
  61.  
  62.         return level[sink] != -1;
  63.     }
  64.  
  65.     int dfs(int currentNode, int minCapacity, int sink) {
  66.         if (currentNode == sink)
  67.             return minCapacity;
  68.  
  69.         for (int& edgeIndex = nextEdgeIndex[currentNode]; edgeIndex < adjList[currentNode].size(); edgeIndex++) {
  70.             Edge& edge = edges[adjList[currentNode][edgeIndex]];
  71.             if (level[edge.to] == level[currentNode] + 1 && edge.capacity > edge.flow) {
  72.                 int bottleneck = dfs(edge.to, min(minCapacity, edge.capacity - edge.flow), sink);
  73.                 if (bottleneck > 0) {
  74.                     edge.flow += bottleneck;
  75.                     edges[adjList[currentNode][edgeIndex] ^ 1].flow -= bottleneck;
  76.                     return bottleneck;
  77.                 }
  78.             }
  79.         }
  80.  
  81.         return 0;
  82.     }
  83.  
  84.     int maxFlow(int source, int sink) {
  85.         int maxFlow = 0;
  86.         while (bfs(source, sink)) {
  87.             fill(nextEdgeIndex.begin(), nextEdgeIndex.end(), 0);
  88.             int bottleneck;
  89.             while ((bottleneck = dfs(source, INT_MAX, sink)) > 0) {
  90.                 maxFlow += bottleneck;
  91.             }
  92.         }
  93.         return maxFlow;
  94.     }
  95. };
  96.  
  97. int getRandomNumber(int minVal, int maxVal) {
  98.     return minVal + rand() % (maxVal - minVal + 1);
  99. }
  100.  
  101. unordered_set<int> generateDoctorHolidays(int numHolidays, int numDays) {
  102.     unordered_set<int> holidays;
  103.     while (holidays.size() < numDays) {
  104.         int holiday = getRandomNumber(1, numHolidays * numDays);
  105.         holidays.insert(holiday);
  106.     }
  107.     return holidays;
  108. }
  109.  
  110.  
  111. string getHolidayDate(int holiday, int numDaysPerMonth) {
  112.     int month = (holiday - 1) / numDaysPerMonth + 1;
  113.     int day = (holiday - 1) % numDaysPerMonth + 1;
  114.     return to_string(month) + "/" + to_string(day);
  115. }
  116.  
  117. void printSchedule(const vector<unordered_map<int, string>>& schedule, int numDaysPerMonth) {
  118.     for (int i = 0; i < schedule.size(); i++) {
  119.         cout << "Doctor " << i + 1 << " schedule: ";
  120.         for (const auto& entry : schedule[i]) {
  121.             //cout << getHolidayDate(entry.first, numDaysPerMonth) << " - " << entry.second << "  ";
  122.             cout << entry.first << " - " << entry.second << "  ";
  123.         }
  124.         cout << endl;
  125.     }
  126. }
  127.  
  128. int main() {
  129.     srand(static_cast<unsigned>(time(0))); // 设置随机数种子
  130.  
  131.     int numDoctors; // 医生数量
  132.     int numHolidays; // 假期数量
  133.     int numDays; // 每个假期的天数
  134.     int maxDutyDays; // 每名医生最多值班的天数
  135.  
  136.     int mo;
  137.     cout << "输入数据规模: ";
  138.     cin >> mo;
  139.     /*
  140.     cout << "输入医生个数: ";
  141.     cin >> numDoctors;
  143.     cout << "输入假期个数: ";
  144.     cin >> numHolidays;
  146.     cout << "输入每个假期的天数: ";
  147.     cin >> numDays;
  149.     cout << "输入每名医生最多值班天数: ";
  150.     cin >> maxDutyDays;
  151.     */
  152.     numDoctors = numHolidays = numDays = maxDutyDays = mo;
  153.     cout << endl;
  154.  
  155.     // 生成每个医生的假日集合
  156.     vector<unordered_set<int>> doctorHolidays(numDoctors);
  157.     for (int i = 0; i < numDoctors; i++) {
  158.         doctorHolidays[i] = generateDoctorHolidays(numHolidays, numDays);
  159.     }
  160.  
  161.     // 输出生成的数据
  162.     //cout << "Number of doctors: " << numDoctors << endl;
  163.     //cout << "Number of holidays: " << numHolidays << endl;
  164.     //cout << "Number of days per holiday: " << numDays << endl;
  165.     //cout << "Maximum duty days per doctor: " << maxDutyDays << endl;
  166.     for (int i = 0; i < numDoctors; i++) {
  167.         cout << "Doctor " << i + 1 << " holidays: ";
  168.         for (int holiday : doctorHolidays[i]) {
  169.             cout << getHolidayDate(holiday, numDays) << " ";
  170.         }
  171.         cout << endl;
  172.     }
  173.  
  174.     // 构建流网络
  175.     int numNodes = numDoctors + numHolidays * numDays + 2; // 医生节点 + 假期节点 + 源点 + 汇点
  176.     int source = 0;
  177.     int sink = numNodes - 1;
  178.     Dinic dinic(numNodes);
  179.  
  180.     // 添加医生节点和源点之间的边
  181.     for (int i = 1; i <= numDoctors; i++) {
  182.         dinic.addEdge(source, i, maxDutyDays);
  183.     }
  184.  
  185.     // 添加假期节点和汇点之间的边
  186.     int nodeOffset = numDoctors;
  187.     // 添加假期节点和汇点之间的边
  188.         for (int i = 1; i <= numHolidays; i++) {
  189.             for (int j = 1; j <= numDays; j++) {
  190.                 dinic.addEdge(nodeOffset + (i - 1) * numDays + j, sink, 1);
  191.             }
  192.         }
  193.  
  194.     // 添加医生节点和假期节点之间的边
  195.     for (int i = 1; i <= numDoctors; i++) {
  196.         for (int j = 1; j <= numHolidays; j++) {
  197.             for (int k = 1; k <= numDays; k++) {
  198.                 if (doctorHolidays[i - 1].count((j - 1) * numDays + k) > 0) {
  199.                     dinic.addEdge(i, nodeOffset + (j - 1) * numDays + k, 1);
  200.                 }
  201.             }
  202.         }
  203.     }
  204.  
  205.     auto start = steady_clock::now();
  206.  
  207.     // 使用Dinic算法求解最大流
  208.     int maxFlow = dinic.maxFlow(source, sink);
  209.  
  210.     auto end = steady_clock::now();
  211.  
  212.     cout << "Maximum flow: " << maxFlow << endl;
  213.  
  214.     // 解析最大流，生成医生的排班方案
  215.     vector<unordered_map<int, string>> schedule(numDoctors);
  216.     for (const auto& edge : dinic.edges) {
  217.         if (edge.from >= 1 && edge.from <= numDoctors && edge.to >= nodeOffset + 1) {
  218.             if (edge.flow > 0) {
  219.                 int doctor = edge.from;
  220.                 int holiday = (edge.to - nodeOffset - 1) / numDays + 1;
  221.                 string date = getHolidayDate(edge.to - nodeOffset, numDays);
  222.                 schedule[doctor - 1][holiday] = date;
  223.             }
  224.         }
  225.     }
  226.     
  227.     
  228.     auto last = duration_cast<microseconds>(end - start);
  229.  
  230.     // 输出医生的排班方案
  231.     printSchedule(schedule, numDays);
  232.     cout << endl << "耗时：" << last.count() * 0.001 << " ms" << endl;
  233.  
  234.     return 0;
  235. }
  236.

（by 归忆）

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/621331
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号