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