_cheng @ 2024-07-26 16:05:59
这是bfs
bool bfs(int st){
while(q.size()) q.pop();
for(int i=1; i<=n; ++i) dep[i] = -1;
for(int i=1; i<=n; ++i) cur[i] = head[i] ;
q.push(st); dep[st] = 0;
while(q.size()){
int p = q.front(); q.pop();
for(int i=head[p]; i; i=e[i].nxt){
if(dep[e[i].to]!=-1 || e[i].w<=0) continue ; //遍历过了, 排掉, 因为要取最短 //边权为0, 排掉, 因为加入后无法增广(瓶颈为0)
dep[e[i].to] = dep[p] + 1;
q.push(e[i].to);
if(e[i].to == en) return 1; //这个时候说明所有<dis[en]的都遍历完了(因为是bfs), 所以就return 1
}
}
return 0; //无论怎么扩大都无法抵达end, 说明管子几乎都装满了, 没有可以增广的路了
}
这是dfs
ll dfs(int x, ll last){ //last: 剩余流量
if(x == en) return last ; //终点的一定可以流出去, 所以剩多少, 留多少
ll mxflow_sum = 0ll; //从这个点出去的最大流们之和
for(int i=cur[x]; i && last; i=e[i].nxt){ //小优化: 剩余0了, 反正流不了, 直接退
cur[x] = i ; //"当前弧"优化: 流满的路径(即e[i-1]), 下次来时不用再遍历, 反正下面的mxflow已经确定了, 已经流满了, 你再来, 也流不进去, 所以就从没流过或流了一半的开始(e[i]及以后)
int v = e[i]. to;
if(dep[v]!=dep[x]+1 || e[i].w<=0) continue ; //不满足层序以及瓶颈为0的都要排掉
ll mxflow = dfs(v, min(e[i].w, last)); //从这个节点到end的最大流
if(mxflow == 0) {dep[v] = -1; continue;} //从这个节点到结尾的增广路最大流为0, 下次要么一样, 要么更小, 所以不可能再对答案有贡献了, 直接堵掉
e[i].w -= mxflow , e[i^1].w += mxflow ; //这一条边也在路径上, 也要减掉mxflow
last -= mxflow, mxflow_sum += mxflow ; //剩余的流(last)要减去这条管子路径的流
}
return mxflow_sum;
}
为什么dfs里, 遍历到一个新点, 也要判断边权是否为0? (if(dep[v]!=dep[x]+1 || e[i].w<=0) continue ;
)边权为0的, 之前bfs不是排掉了吗?
等待dalao的出现awa
by Obijeb @ 2024-07-26 16:17:57
@_cheng 在dfs推流的过程中,可能重复经过一些点,也会有重复的边
一条边可能在上一次经过该点的时候被流干了
by _cheng @ 2024-07-26 16:32:11
O, 对耶, e[i].w会重新赋值, 流完了就是0了
by _cheng @ 2024-07-26 16:32:38
感谢