dinic,为什么反向边要加上流量.

P3376 【模板】网络最大流

hjxddl @ 2022-01-26 16:23:12

for(int i=cur[x];i;i=nxt[i]){
    cur[x]=i;
    int y=ver[i];
    if(data[i]&&d[y]==d[x]+1){
        ll Min=dfs(y,min(rest,1ll*data[i]));
        data[i]-=Min;
//      data[i^1]+=Min;
        rest-=Min;
        if(!rest)break;
    }
}

如题,就是那一句data[i^1]+=Min.很多代码都写上了那一句,解释是用来反悔啦,回收流量啦什么什么的,但是完全没有用上啊,在这里//掉之后也可以过这个板子,还是说在某些特定题型里面会有用???


by RainFestival @ 2022-01-26 16:24:59

请不要鞭尸这个数据水的模板了。


by MeowScore @ 2022-01-26 16:25:40

@z1462478610 数据太水了,不要在意


by xyf007 @ 2022-01-26 16:53:58

@z1462478610 当然要加啊,不加是错的。


|