Shymeleaf @ 2022-11-27 20:49:40
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/**
* @author wangqiang6
* @version 0.1
* @description EK 算法
* @date 2022-11-27
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] nmst = br.readLine().split(" ");
int n = Integer.parseInt(nmst[0]);
int m = Integer.parseInt(nmst[1]);
int s = Integer.parseInt(nmst[2]);
int t = Integer.parseInt(nmst[3]);
Main edmondKarp = new Main();
edmondKarp.resolve(n, m, s, t, br);
}
public void resolve (int n, int m, int s, int t, BufferedReader br) throws IOException {
// 1. 建图
buildGraph(n, m, br);
// 2. ek 算法开始
pre = new int[100000]; // 因为题目:节点编号都是正数 1 ~ n;所以数组大小开到 n + 1
minW = new long[100000]; // 同上
long ans = 0;
while (bfs(s, t)) {
ans += minW[t];
modifyEdgeWeight(s, t);
}
System.out.println(ans);
}
/**
* 根据 pre 数组,从 target 出发,沿着新求出来的增广路径追溯回 source,
* 修改增广路径每一条边的正向权重(剩余容量)和反向权重(剩余容量)
* @param source
* @param target
*/
public void modifyEdgeWeight(int source, int target) {
int cur = target;
while (cur != source) {
int preEdge = pre[cur]; // pre 记录的是前驱边,取出来的是前驱边
// 正向边权值修正
// 找到一条增广路径后,从 source 至 target 最小的 边的剩余容量 已求出,即 minW[target]
// 随着 边剩余容量的 修改,从 source 可达 target 的所有路径上必定都会出现 某条边 剩余容量为 0,算法收敛
edgeWeight[preEdge] -= minW[target];
// 反向边权值修正
// 【细节4】在建图的时候,是添加一条边,就同时再添加其对应的反向边
// 因此,下标 0 2 4 6 ... 2n 存的都是图中切实存在的边,而 1 3 5 7 ... 2n ^ 1 存的都是【同时添加的反向边】
// 这里用 ^ 表示 +,因为偶数 + 1 肯定不会产生进位
edgeWeight[preEdge ^ 1] += minW[target];
cur = edgeTo[preEdge ^ 1]; // 前一个节点就是 preEdge 对应边的反向边的目标节点 edgeTo[preEdge ^ 1]
}
}
// pre[i] 节点 i 的前驱边
public int[] pre; // pre[i] 为 到节点 i 所经过的与 i 相连的边(同时可以标志 节点 i 是否被访问过
// minW[i] 至点 i 为止,最小的【边的剩余容量】
public long[] minW;
/**
* source 到 target 寻找增广路径
* @param source
* @param target
* @return
*/
public boolean bfs (int source, int target) {
Arrays.fill(pre, -2); // -2 为节点 i 还未被访问过的标志
Queue<Integer> queue = new LinkedList<>();
pre[source] = -1; // 源节点的前驱边记为任意不存在的边,同时区别于 -2(未访问标志)即可
queue.add(source);
minW[source] = Integer.MAX_VALUE; // 重置【至 source 为止 最小的【边的剩余容量】】为 最大值
while (!queue.isEmpty()) {
int curNode = queue.poll();
for (int e = head[curNode]; e != -1; e = nextEdge[e]) {
int nextNode = edgeTo[e];
if (pre[nextNode] == -2 && edgeWeight[e] > 0) { // 边关联的下一个节点没被访问过 && 边的剩余容量大于 0 才考虑
// 更新路径上的最小剩余容量
minW[nextNode] = Math.min(minW[curNode], edgeWeight[e]); // 【细节3】minW[i]的更新是直接算的(不用重置)
queue.add(nextNode);
pre[nextNode] = e;
if (nextNode == target) { // 找到了任意一条增广路径
return true;
}
}
}
}
return false;
}
/**
* 邻接表存图
*/
// 与每个节点关联的第一条边
public int[] head;
// 每条边指向的节点
public int[] edgeTo;
// 每条边的权重
public long[] edgeWeight;
// 每条边在head[i] 链表中的下一条边
public int[] nextEdge;
// 当前边的数量
public int nEdge;
// 节点总数
public int nNode;
// 处理重边的辅助数组 key from,to | value edgeNo
public Map<String, Integer> duplicateEdgeHelper;
/**
* 建图
* @param n 节点数量
* @param m 边数量
* @param br
*/
public void buildGraph(int n, int m, BufferedReader br) throws IOException {
head = new int[100000]; // 【细节2】节点编号为正整数,因此 节点编号从 1 ~ n
Arrays.fill(head, -1); // head 初始化,所有节点都不与任何边关联
edgeTo = new int[200000]; // 【细节5】每条边都有其对应的反向边,因此数组大小为 2 * m
edgeWeight = new long[200000]; // 同上
nextEdge = new int[200000]; // 同上
nNode = n;
duplicateEdgeHelper = new HashMap<>();
for (int i = 0; i < m; i ++) {
String[] inputs = br.readLine().split(" ");
int from = Integer.parseInt(inputs[0]);
int to = Integer.parseInt(inputs[1]);
int weight = Integer.parseInt(inputs[2]);
// 正向边
addEdge(from, to, weight);
// 反向边
addEdge(to, from, 0);
}
}
public void addEdge(int from, int to, int weight) {
if (duplicateEdgeHelper.containsKey(from + "," + to)) {
// 【细节1】重复边权值累加,且 由于重边权值相加可能产生溢出,edgeWeight 需为 long[]
edgeWeight[duplicateEdgeHelper.get(from + "," + to)] += weight;
return ;
}
edgeTo[nEdge] = to;
edgeWeight[nEdge] = weight;
nextEdge[nEdge] = head[from];
head[from] = nEdge;
duplicateEdgeHelper.put(from + "," + to, nEdge ++);
}
}