未特殊强调下,本帖子的“指针”指“迭代器”。
用 vector+指针写的网络流,错了,隔壁老王说是最后结束调用析构函数出了问题,司机小李说 add 函数有一大堆问题,三年级的小明说是 vector 的 push_back 可能会使 end(),begin() 那些指针失效。
得分分布:3×AC + 7×RE + 2×WA,说明大数据的时候出了问题,三年级的小明的说法可能就具有说服力,但是怎么改想不明白,查了手册也没查到什么。
代码(C++20,如果使用 C++20 以下版本可能会出现隔壁老王描述的问题):
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, s, t;
struct Edge {
int to, w;
vector<Edge>::iterator rev;
};
vector<Edge> edges[30001];
vector<Edge>::iterator now[30001];
long long dis[30001], q[30001], front, rear;
void add(int u, int v, int z) {
edges[u].push_back((Edge){v, z});
edges[v].push_back((Edge){u, 0, prev(edges[u].end())});
(edges[u].rbegin()) -> rev = prev(edges[v].end()); // 这个地方我和司机小李有很大的争论。
}
int bfs() {
for (int i = 1; i <= n; ++i) {
dis[i] = 1ll << 60;
now[i] = edges[i].begin();
}
q[front = rear = 1] = s;
dis[s] = 1;
now[s] = edges[s].begin();
while (rear + 1 != front) {
int fx = q[front++];
for (auto e = edges[fx].begin(); e != edges[fx].end(); e ++ ) {
int i = e -> to;
if (e -> w > 0 && dis[i] == (1ll << 60)) {
dis[i] = dis[fx] + 1;
q[++rear] = i;
if (i == t) return 1;
}
}
}
return 0;
}
long long dfs(int i, long long sum) {
if (i == t) return sum;
long long res = 0, k;
for (auto e = now[i]; e != edges[i].end(); e ++ ) {
if (!sum) return res;
int j = e -> to;
now[i] = e;
if (e -> w > 0 && dis[j] == dis[i] + 1) {
k = dfs(j, min(sum, e -> w));
if (k == 0) dis[j] = 1ll << 60;
(e -> w) -= k;
(e -> rev -> w) += k;
res += k;
sum -= k;
}
}
return res;
}
signed main() {
scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
for (int i = 1; i <= m; ++i) {
int u, v, w;
scanf("%lld%lld%lld", &u, &v, &w);
add(u, v, w);
}
long long ans = 0;
while (bfs()) ans += dfs(s, 1ll << 60);
printf("%lld\n", ans);
//return 0; // 隔壁老王建议改的地方
}