想请问一下各位大佬我这段dinic算法哪里写的有问题吗,只能通过部分测试点,自己排错半天没发现哪里有错。
#include <bits/stdc++.h>
using namespace std;
class Edge {
public:
int to;
long long weight;
int next;
Edge(int to, long long weight, int next) : to(to), weight(weight), next(next) {}
Edge() {};
};
int m, n, S, T, cnt = 1;
vector<Edge> graph;
vector<int> level, head;
void addEdge(int from, int to, long long weight) {
graph[++cnt] = Edge(to, weight, head[from]);
head[from] = cnt;
}
bool bfs() {
level = vector<int>(n, 0);
level[S] = 1;
queue<int> queue;
queue.emplace(S);
while (!queue.empty()) {
int u = queue.front();
queue.pop();
for (int i = head[u]; i; i = graph[i].next) {
int v = graph[i].to;
long long weight = graph[i].weight;
if (!level[v] && weight) {
level[v] = level[u] + 1;
if (v == T) return true;
queue.emplace(v);
}
}
}
return false;
}
long long dfs(int u, long long inFLow) {
if (u == T) return inFLow;
long long outFlow = 0;
for (int i = head[u]; i; i = graph[i].next) {
int v = graph[i].to;
long long weight = graph[i].weight;
if (level[v] == level[u] + 1 && weight) {
long long flow = dfs(v, min(weight, inFLow));
graph[i].weight -= flow;
graph[i ^ 1].weight += flow;
inFLow -= flow;
outFlow += flow;
if (!inFLow) break;
}
}
if (outFlow == 0) level[u] = 0;
return outFlow;
}
long long dinic() {
long long maxFlow = 0;
while (bfs()) {
maxFlow += dfs(S, LONG_LONG_MAX);
}
return maxFlow;
}
int main() {
cin >> n >> m >> S >> T;
head = vector<int>(n + 1, 0);
graph = vector<Edge>(2 * m + 2);
for (int i = 0; i < m; ++i) {
int from, to, weight;
cin >> from >> to >> weight;
addEdge(from, to, weight);
addEdge(to, from, 0);
}
cout << dinic();
}