请求管理员加强数据

P3376 【模板】网络最大流

Mosklia @ 2018-09-03 08:58:14

这是我学习\text{Dinic}算法,写它的\text{DFS}时发现的一个问题:
我第一次写DFS时这么写的:

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道题:P3376,P2740,P3381(3381需要做一些修改,但是//-----!-----标记的3行没改过)。
把标记的return ans改成return flow之后,都变成了WA
但是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

的测试结果也体现了这一点(正确答案75,我的代码输出100)。
然而上述3题的数据均没有反映这一点。故希望管理员能够帮忙处理一下这3题(P3376,P2740,P3381)的数据,使之可以更加全面地检验出代码中问题。


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不加反边这道题都能过。。。


|