一个指针怪物写的网络流求调,RE+WA
查看原帖
一个指针怪物写的网络流求调,RE+WA
726525
CuteChat楼主2024/4/6 11:59

未特殊强调下,本帖子的“指针”指“迭代器”。

用 vector+指针写的网络流,错了,隔壁老王说是最后结束调用析构函数出了问题,司机小李说 add 函数有一大堆问题,三年级的小明说是 vector 的 push_back 可能会使 end(),begin() 那些指针失效。

得分分布:3×\timesAC + 7×\timesRE + 2×\timesWA,说明大数据的时候出了问题,三年级的小明的说法可能就具有说服力,但是怎么改想不明白,查了手册也没查到什么。

代码(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; // 隔壁老王建议改的地方
}
2024/4/6 11:59
加载中...