经过判断是因为结点还未推送到汇点 t 就将余流退回了源点 s,请问代码逻辑有什么问题吗?
Hack
input:
10 30 3 7
10 2 18652
8 9 2560
8 9 13734
5 6 23138
9 7 29606
5 8 21673
1 9 11596
3 2 9441
3 7 4829
5 8 24437
1 2 31111
4 10 26213
2 7 31808
1 9 10841
6 8 10758
3 5 11887
4 2 1362
4 1 18182
4 8 18156
10 6 11015
2 7 2640
10 6 27726
10 6 21615
5 1 5959
3 1 19857
5 4 1862
8 9 13830
3 10 22152
4 10 5221
5 2 24065
output:
68166
wrong output:
26157
code:
#include <bits/stdc++.h>
using namespace std;
#define inf 1000000000000000
#define V 50010
#define E 1000010
typedef long long int ll;
struct edge {
public:
int to, next;
ll capa;
};
int cnt = 0, head[V]; int n, m; vector<edge>node(E);
inline void add(int fir, int nxt, ll w) {
node[cnt].to = nxt;
node[cnt].capa = w;
node[cnt].next = head[fir];
head[fir] = cnt; ++cnt;
}
int s, t, dep[V], gap[V]; queue<int>que; ll sum = 0; ll cur[V];
bool inque[V];
inline void initing() { memset(dep, -1, V * sizeof(int)); }
inline void bfs() {
int fro, ito;
que.push(t); dep[t] = 0; ++gap[dep[t]];
while (!que.empty()) {
fro = que.front(); que.pop();
for (register int i = head[fro]; i != -1; i = node[i].next) {
ito = node[i].to;
if (dep[ito] == -1) {
dep[ito] = dep[fro] + 1;
que.push(ito);
++gap[dep[ito]];
}
}
}
}
struct cmp {
public:
inline bool operator()(int a, int b) {return dep[a] < dep[b];}
};
priority_queue<int, vector<int>, cmp>hlpp;
void push(int v) {
for (int i = head[v]; i != -1; i = node[i].next) {
if (!cur[v])return;
if (dep[v] == dep[node[i].to] + 1 && node[i].capa) {
ll ls = min(cur[v], node[i].capa);
cur[v] -= ls, cur[node[i].to] += ls;
node[i].capa -= ls, node[i ^ 1].capa += ls;
if (!inque[node[i].to] && node[i].to != s && node[i].to != t) {
hlpp.push(node[i].to);
inque[node[i].to] = true;
}
}
}
}
void relable(int v) {
dep[v] = n + 1;
for (register int i = head[v]; i != -1; i = node[i].next) {
if (node[i].capa && dep[v] > dep[node[i].to] + 1)
dep[v] = dep[node[i].to] + 1;
}
}
ll HLPP() {
cur[s] = inf; initing(); bfs();
int np; int v; ll w; ll ans = 0;
for (int i = head[s]; i != -1; i = node[i].next) {
v = node[i].to; w = node[i].capa;
cur[s] -= w; cur[v] += w;
node[i].capa -= w;
node[i ^ 1].capa += w;
if (v != s && v != t) { hlpp.push(v); inque[v] = true; }
}
while (!hlpp.empty()) {
np = hlpp.top(); hlpp.pop();
relable(np);
inque[np] = false;
push(np);
if (cur[np]) {
if (--gap[dep[np]] == 0) {
for (int i = 1; i <= n; i++)
if (i != s && i != t && dep[i] > dep[np] && dep[i] < n + 1)
dep[i] = n + 1;
}
relable(np);
++gap[dep[np]];
hlpp.push(np);
inque[np] = true;
}
}
return cur[t];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(); cout.tie();
memset(head, -1, V * sizeof(int));
cin >> n >> m >> s >> t;
int f, l; ll w;
for (register int i = 0; i < m; i++) {
cin >> f >> l >> w;
add(f, l, w);
add(l, f, 0);
}
cout << HLPP();
return 0;
}