lab要求如下：
1.代码实现思路
-
图的构建
-
使用邻接表
adjacencyList来存储图的结构，每个节点对应一个列表，列表中存储从该节点出发的所有边。 -
通过
addEdge方法添加有向边及其反向边，同时设置正向边和反向边的相互引用。
-
-
最小费用最大流算法
-
算法主体在
minCostMaxFlow方法中，使用循环不断寻找增广路径，直到无法找到从源点到汇点的路径为止。 -
在每次循环中，使用 Dijkstra 算法来寻找从源点到汇点的最小费用路径，通过维护距离数组
dist、前驱边数组parent和优先队列pq来实现。 -
找到最小费用路径后，确定增广路径上的最小剩余容量
flow，然后沿着增广路径更新流量和费用。
-
static final int INF = Integer.MAX_VALUE; // 无穷大
// 边的定义
static class Edge {
int start, end, capacity, cost, flow; // 起点、终点、容量、费用、流量
Edge residual; // 反向边
public Edge(int start, int end, int capacity, int cost) {
this.start = start;
this.end = end;
this.capacity = capacity;
this.cost = cost;
this.flow = 0;
}
// 剩余容量
int remainingCapacity() {
return capacity - flow;
}
// 增加流量
void augmentFlow(int value) {
this.flow += value;
this.residual.flow -= value;
}
}
static int nodeCount, edgeCount, source, sink; // 节点数、边数、源点、汇点
static List<Edge>[] adjacencyList; // 邻接表
// 添加有向边和反向边
static void addEdge(int from, int to, int capacity, int cost) {
if (capacity < 0) {
throw new IllegalArgumentException("Capacity cannot be negative.");
}
Edge forwardEdge = new Edge(from, to, capacity, cost);
Edge backwardEdge = new Edge(to, from, 0, -cost);
forwardEdge.residual = backwardEdge;
backwardEdge.residual = forwardEdge;
adjacencyList[from].add(forwardEdge); // 正向边
adjacencyList[to].add(backwardEdge); // 反向边
}关键算法：
整体思路：通过不断寻找最小费用增广路径并更新流量和费用，直到不存在从源点到汇点的增广路径为止。找到一条从源节点到汇点的路径。计算路径上的最小容量，并更新每个边的流量。沿路径反向更新每个边的残余容量。如果找不到一条路径，则算法结束。否则，重复循环，直到找不到更多路径，计算最大流和最小成本。
// 最小费用最大流算法
static int[] minCostMaxFlow() {
int totalFlow = 0, totalCost = 0;
while (true) {//Dijkstra算法
int[] dist = new int[nodeCount + 1];
Edge[] parent = new Edge[nodeCount + 1];
Arrays.fill(dist, INF);
dist[source] = 0;
boolean[] visited = new boolean[nodeCount + 1]; // 访问标记
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(a -> dist[a]));
pq.add(source); // 只添加源点
while (!pq.isEmpty()) {
int u = pq.poll();
// 如果该节点已被访问，跳过
if (visited[u]) continue;
visited[u] = true; // 标记为已访问
for (Edge edge : adjacencyList[u]) {
if (edge.remainingCapacity() > 0 && dist[edge.end] > dist[u] + edge.cost) {
dist[edge.end] = dist[u] + edge.cost;
parent[edge.end] = edge;
// 只有在未访问的情况下才添加到优先队列
if (!visited[edge.end]) {
pq.add(edge.end);
}
}
}
}
// 如果无法到达汇点，退出
if (dist[sink] == INF) break;
// 找到增广流量
int flow = INF;
for (int v = sink; v != source; v = parent[v].start) {
flow = Math.min(flow, parent[v].remainingCapacity());
}
// 增广路径上的流量与费用更新
for (int v = sink; v != source; v = parent[v].start) {
parent[v].augmentFlow(flow);
totalCost += flow * parent[v].cost;
}
totalFlow += flow;
}
return new int[]{totalFlow, totalCost}; // 直接返回最大流和最小费用
}运行结果示例：
2.复杂度分析
-
时间复杂度：每次执行 Dijkstra 算法的时间复杂度是 O((E + V) log V)，而最多执行
O(F)次。综合时间复杂度为：O(F⋅(E+V)logV)。其中F是最大流量，E是边的数量，V是节点数量。 -
空间复杂度：空间复杂度主要由邻接表，
dist[]数组，parent[]数组，visited[]数组，PriorityQueue，边的存储构成。因此，总体空间复杂度为O(V+E)。
