2025年Edmond-Krap算法

科技前沿 • 2025-02-18 16:24 • 阅读 83

大家好，我是讯享网，很高兴认识大家。

Edmond-Krap算法

从源点到终点的路径有若干条，无法一下子将所有可以有水流通过路径全部找出。也无法直接贪心去确定，因为路径是怎样的是无法确定的贪心也无从寻找规律。这时候只剩一种方法——搜索，但是搜索过程对于每次出现一条从源点到终点的路时，会对当前部分管道流量容量有影响的，搜索需要回溯以保证找出的路线不是最优后能有其他选择。但是回溯有缺点，每次整条路都去掉了，那样效率比较低。

我们把回溯的想法如果换一种思维，把通过流量p的管道增加一条流量也为p的反向管道，这样并不需要把完全回到之前的状态，反向管道如果再后来被利用了，那和回溯的作用没有区别。

看这个例子：
A为源点，D为终点。
每一条边的容量都为1.

在这里插入图片描述
讯享网

如果搜索，只能找到如下一条边。在这里插入图片描述
如果加反向通道（蓝色边）
那可以再搜索一次就得到了通道，宏观上表现为A->B->D和A->C->D,边BC
是没有经过的，和回溯是一致的。

在这里插入图片描述

姑且这样理解。其实Edmond-Krap算是Fold-Fulkerson的一种实现方式，上面说的就是Fold-Fulkerson的大致思路。

Edmond-Krap每次搜索出一条路，加入总的路径，修改通道的剩余容量和反向通道的剩余容量，没有其他的任何操作。

#include<bits/stdc++.h> using namespace std; string s; const int maxn = 1e5+5; const int INF = 1e9; typedef struct Edge{ 
    int next,to,w; }E; E e[maxn<<1]; int head[maxn],flow[maxn],edg[maxn],cnt = -1,pre[maxn],S,T,N,M; void add(int u,int v,int w){ 
    e[++cnt].to=v; e[cnt].w=w; e[cnt].next=head[u]; head[u]=cnt; } bool bfs(){ 
   //寻找一条源点到终点的通路 for(int i = 1;i <= N;i++){ 
    pre[i] = edg[i] = -1; flow[i] = INF; } pre[S] = 0; queue<int> q; q.push(S); while(!q.empty()){ 
    int u=q.front(); q.pop(); if(u==T)break; for(int i=head[u];~i;i=e[i].next){ 
    int v=e[i].to; if(e[i].w>0&&pre[v]==-1){ 
   //当前管道还有容量且点v这次搜索没有被其他路利用 pre[v]=u; edg[v]=i; flow[v]=min(flow[u],e[i].w);//通路中最小的量为整条路的最大值 q.push(v); } } } return pre[T]!=-1; } int EK(){ 
    int ans = 0; while(bfs()){ 
    int x=T; while(x!=S){ 
   //修改管道剩余容量 e[edg[x]].w-=flow[T]; e[edg[x]^1].w+=flow[T]; x=pre[x]; } ans+=flow[T]; } return ans; } int main(){ 
    cin >> N >> M; for(int i = 1;i <= N;i++)head[i] = -1; for(int i = 1;i <= M;i++){ 
    int x,y,w; cin >> x >> y >> w; add(x,y,w); add(y,x,0); } //for(int i = 1;i <= N;i++)head[i] = -1; S = 1;T = N; int ans = EK(); cout << ans <<endl; return 0; }

讯享网

2025年Edmond-Krap算法

Edmond-Krap算法

相关推荐