无可奈何WA落去,似曾相识T归来。
准确的说不是T了,是不输出结果。
抄的是 https://www.luogu.com.cn/paste/hakjys6r
这个代码。 到底哪里抄错了啊……悬关 /bx
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1ll << 30;
int top = 1, head[10100], n, m, s, t;
int e[10100], h[10100], cnth[20100]; // 每个点对应的余流,高度;每个高度有多少个点
struct cmp {
inline bool operator () (int a, int b) const {
return h[a] < h[b];
}
};
struct Node {
int v, val, Next;
} node[400100];
inline void add(int u, int v, int val) {
node[++top].v = v; node[top].val = val; node[top].Next = head[u]; head[u] = top;
node[++top].v = u; node[top].val = 0; node[top].Next = head[v]; head[v] = top;
}
int inque[11000];
void bfs() {
memset(h, 0x3f, sizeof(h));
h[t] = 0;
queue <int> q; q.push(t);
while (q.size()) {
int u = q.front(); q.pop();
inque[u] = 0;
for (int i = head[u]; i; i = node[i].Next) {
int d = node[i].v;
if (node[i ^ 1].val && h[d] > h[u] + 1) { // 反向跑
h[d] = h[u] + 1;
if (inque[d] == 0) {
q.push(d);
inque[d] = 1;
}
}
}
}
}
priority_queue <int, vector<int>, cmp> q;
inline void push_(int u) { // 推流
for (int i = head[i]; i; i = node[i].Next) {
int d = node[i].v;
if (node[i].val && h[d] + 1 == h[u]) { // 可以推流
int minn = min(node[i].val, e[u]);
node[i].val -= minn;
node[i ^ 1].val += minn;
e[u] -= minn; e[d] += minn;
if (inque[d] == 0 && d != s && d != t) {
q.push(d);
inque[d] = 1;
}
if (e[u] == 0) break; // 已经推完了
}
}
}
inline void relabel(int u) { // 翻译:重新贴标签。把 u 的高度更改为与 u 相邻的最低点的高度 + 1
h[u] = inf;
for (int i = head[u]; i; i = node[i].Next) {
int d = node[i].v;
if (node[i].val && h[d] + 1 < h[u]) h[u] = h[d] + 1;
}
}
int HLPP() {
bfs();
if (h[s] == 0x3f3f3f3f) return 0; // s 与 t 不连通
h[s] = n;
for (int i = 1; i <= n; i++)
if (h[i] < 0x3f3f3f3f) cnth[h[i]] ++; // 统计 各个高度的点数,下标不要越界
for (int i = head[s]; i; i = node[i].Next) { // 从 s 向周围点推流
int d = node[i].v, minn = node[i].val;
if (minn) {
e[s] -= minn; e[d] += minn;
node[i].val -= minn; node[i ^ 1].val += minn;
if (d != t && inque[d] == 0 && d != s) {
q.push(d);
inque[d] = 1;
}
}
}
while(q.size()) {
int u = q.top(); q.pop();
inque[u] = 0;
push_(u);
if (e[u]) { // 还有余流
if (--cnth[h[u]] == 0) // gap优化
for (int i = 1; i <= n; i++)
if (i != s && i != t && h[i] > h[u] && h[i] <= n)
h[i] = n + 1; //标记无法到达
relabel(u);
cnth[h[u]] ++;
q.push(u); inque[u] = 1;
}
}
return e[t];
}
signed main() {
//cin.tie(0); ios::sync_with_stdio(0);
cin >> n >> m >> s >> t;
for (int i = 1; i <= m; i++) {
int u, v, val;
cin >> u >> v >> val;
add(u, v, val);
}
cout << HLPP();
}