奇怪的RE
查看原帖
奇怪的RE
678858
ShiRoZeTsuHL卜奎BBQ!楼主2023/8/10 17:15

以下是我在写 dinic 时遇到的一个小问题:

int dfs(int u, int sum) {
	if(u == t) return sum;
	int k, res = 0;
	for(int i = now[u]; i && sum; i = e[i].nxt) {
		now[u] = i;
		int v = e[i].to;
		if(e[i].w > 0 && dis[v] == dis[u]+1) {
			k = dfs(v, min(sum, e[i].w));
			if(!k) dis[v] = inf;
			else {
				e[i].w -= k;
				e[i^1].w += k;
				res += k;
				sum -= k;
				to[u] = v;
                //**************
				if(u != s) tag[v-n] = true;
                //**************
			}
		}
	}
	return res;
}

然后主函数输出路径的时候,判断每个点的 tag[i], 结果这样交上去拿到了 #2 #6 #8 RE的好成绩,于是我将 if(u != s) tag[v-n] = true; 改成了 if(u != s) tag[v] = true; ,然后再主函数输出时判断 tag[i+n],结果就 AC了,这里有点看不懂,有大佬给解释一下吗?谢谢

2023/8/10 17:15
加载中...