Mosklia @ 2018-09-03 08:58:14
这是我学习
我第一次写
int dfs(int p, int flow, int t) {
if(!flow || p == t) return flow;
int ans = 0, temp = 0;
for(int i = pt[p].cur; i; i = ph[i].next) {
int x = ph[i].end;
pt[p].cur = i;
if(ph[i].cap && pt[x].dist == pt[p].dist + 1)
if(temp = dfs(x, std::min(flow, ph[i].cap), t)) { //-----!-----
ph[i].cap -= temp;
ph[i ^ 1].cap += temp;
ans += temp;
if(ans >= flow)//-----!-----
return ans;//-----!-----
}
}
return ans;
}
发现可以通过//-----!-----
标记的3行没改过)。
把标记的return ans
改成return flow
之后,都变成了
但是ans
不应当大于flow
,在ans >= flow
时返回flow
才是正确的……
请教学长,学长一眼看出是第一个标记处min
应该写成
std::min(flow - ans, ph[i].cap);
否则在向下递归时,会因为没有考虑之前损耗的那部分流量而出错。
随后对于自造的这组数据:
3 3 1 3
1 2 75
2 3 50
2 3 50
的测试结果也体现了这一点(正确答案
然而上述
by Mosklia @ 2018-09-03 08:58:31
@chen_zhe
by w_x_c_q @ 2018-09-03 10:36:33
%
by caeious @ 2018-09-22 18:49:25
@Sparky_14145 @钱逸凡 真的,我在看某谷日报讲解dinic的标程时发现也有如上的锅:
if(rlow=dfs(d,min(low,node[i].val))){
used+=rlow;//该点使用的流量增加
node[i].val-=rlow;
node[i^1].val+=rlow;
if(used==low)break;//该点流量满了,没必要再找了
}
但是他的提交也过了。。。
希望管理员处理一下,至少把日报上的标程改好吧。
by 钱逸凡 @ 2018-09-23 13:21:35
对不起,之前写日报时没仔细检查,已修正。
我也不知道为什么之前那么写可以过,求管理员加强数据
by Floatiy @ 2018-10-04 20:10:55
求加强@chen_zhe
比如我随便造的数据
8 10 7 8
7 1 3
7 2 2
7 3 2
4 8 2
5 8 2
6 8 2
1 5 1
2 6 1
3 5 1
3 4 1
也能卡掉我在这道题上过了的代码。 本来Dinic细节就容易错,数据不行的话太容易误导了
by swhsz @ 2018-10-19 11:23:16
其实dinic不加反边这道题都能过。。。