以下是我在写 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了,这里有点看不懂,有大佬给解释一下吗?谢谢