为什么当前弧优化这样会很慢?
查看原帖
为什么当前弧优化这样会很慢?
383782
StarPatrick楼主2023/5/3 20:26
for (int p=cur[i];p<v[i].size();p++) {
	cur[i] = p;
	if (v[i][p].u&&dis[v[i][p].i]==dis[i]+1) {
		ll flow = dfs(v[i][p].i, min(u, v[i][p].u));
		u-=flow, all+=flow;
		v[i][p].u-=flow;
		v[v[i][p].i][v[i][p].back].u+=flow;
		if (!u) return all;
	}
}

这个59ms

for (int p=cur[i];p<v[i].size();p++) {
	cur[i] = p+1;
	if (v[i][p].u&&dis[v[i][p].i]==dis[i]+1) {
		ll flow = dfs(v[i][p].i, min(u, v[i][p].u));
		u-=flow, all+=flow;
		v[i][p].u-=flow;
		v[v[i][p].i][v[i][p].back].u+=flow;
		if (!u) return all;
	}
}

这个659ms,仅仅改了这一个地方

cur[i] = p+1;

理应说来应该更快啊,为啥慢了好多?

2023/5/3 20:26
加载中...