精华内容
下载资源
问答
  • 增广路算法入门

    千次阅读 2019-08-19 10:51:00
    增广路定理: 我们用未覆盖点来表示不与任何匹配边邻接的点,其他点为匹配点,即恰好和一条匹配边邻接的点。从未覆盖点出发,依次经过非匹配边,匹配边,非匹配边,匹配边…所得的路称为交替路。如果交替路的终点是...

    增广路定理:
    我们用未覆盖点来表示不与任何匹配边邻接的点,其他点为匹配点,即恰好和一条匹配边邻接的点。从未覆盖点出发,依次经过非匹配边,匹配边,非匹配边,匹配边…所得的路称为交替路。如果交替路的终点是一个未覆盖点,则称这条交替路为一条增广路,非匹配边比匹配边多一条。

    增广路的作用是改进匹配,假设我们已经找到一个匹配,如何判断他 是否是最大匹配?看增广路,如果有一条增广路,呢么把此路上的匹配边和非匹配边互换,得到的匹配边比刚才多一条。反之,若找不到增广路,则当前为最大匹配

    一个匹配是最大匹配的充要条件是不存在增广路,这个充要条件适用于任意图。
    

    增广路算法:
    根据增广路定理,最大匹配可以通过反复寻找增广路来求解,如何找到答案?根据定义首先找到一个未覆盖的点u作为起点,设这个u是X的结点。接下来需要选一个从u出发的非匹配边(u,v),达到Y结点v。如果v是未覆盖点。说明我们成功找到了一条增广路,如果v是匹配点,那我们下一不得走匹配边,因为一个匹配点恰好与一个匹配边邻接。设匹配点v邻接的匹配边的另一端点left[v],呢么可以理解从u直接走到了left[v],而这个left[v]也是一个X结点。如果始终没有找到覆盖点,最后会扩展出一颗匈牙利树。

    这样,我们得到了一个算法,即每次选一个未覆盖点u进行DFS,注意,如果找不到u开头的增广路,则换一个未覆盖点进行DFS,且以后再也不从u出发找增广路。换句话说,如果以后存在一个从出发的增广路,呢么现在就找得到。
    代码:

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=600+5;
    bool line[maxn][maxn];
    //line[x][y]=true表示x号女生喜欢y男生(边)
    int boy[maxn];
    //存储y号男生匹配边另一端的匹配点女生,如果是未覆盖点则为0
    bool use[maxn];
    //存储y号男生是否在这条交替路上被使用过,男生是否被别人喜欢
    int k,n,m;
    bool dfs(int x)
    {
    
        for(int j=1;j<=m;j++)
        {
            if(line[x][j]&&!use[j])
               {
                   use[j]=true;
                   if(!boy[j]||dfs(boy[j]))
                   {
                       //满足上面的判断语句说明找到了增广路
                       //即终点是未覆盖点的交替路
                       boy[j]=x;
                       return true;
    
                   }
               }
            //该条路不是增广路
        }
    
        return false;
    
    }
    
    int main()
    {
        while(cin>>k)
        {
            if(!k)
                break;
            cin>>n>>m;
            int x,y;
            int ans=0;
            memset(line,false,sizeof(line));
            memset(boy,0,sizeof(boy));
            while(k--)
            {
                cin>>x>>y;
                line[x][y]=true;
            }
            for(int i=1;i<=n;i++)
            {
                memset(use,false,sizeof(use));
                if(dfs(i))
                    ans++;
            }
            cout<<ans<<endl;
        }
    
        return 0;
    }
    
    展开全文
  • 增广路简介

    千次阅读 2018-05-03 18:26:15
    增广路要知道这些干货①P的路径长度必定为奇数,第一条边和最后一条边都不属于M②P经过取反操作可以得到一个更大的匹配M③M为G的最大匹配当且仅当不存在相对于M的增广路径我理解的还不够深,这里不兹论述,详情参考...

    增广路要知道这些干货

    ①P的路径长度必定为奇数,第一条边和最后一条边都不属于M

    ②P经过取反操作可以得到一个更大的匹配M

    ③M为G的最大匹配当且仅当不存在相对于M的增广路径

    我理解的还不够深,这里不兹论述,详情参考https://blog.csdn.net/reid_zhang1993/article/details/44080167

    这里介绍一种增广路求法和网络流(最大)算法

    首先,假如所有边上的流量都没有超过容量(不大于容量),那么就把这一组流量,或者说,这个流,称为一个可行流。一个最简单的例子就是,零流,即所有的流量都是0的流。

    我们就从这个零流开始考虑,假如有这么一条路,这条路从源点开始一直一段一段的连到了汇点,并且,这条路上的每一段都满足流量<容量,注意,是严格的<,而不是<=。那么,我们一定能找到这条路上的每一段的(容量-流量)的值当中的最小值delta。我们把这条路上每一段的流量都加上这个delta,一定可以保证这个流依然是可行流,这是显然的。

    这样我们就得到了一个更大的流,他的流量是之前的流量+delta,而这条路就叫做增广路。

    我们不断地从起点开始寻找增广路,每次都对其进行增广,直到源点和汇点不连通,也就是找不到增广路为止。当找不到增广路的时候,当前的流量就是最大流,这个结论非常重要。

    寻找增广路的时候我们可以简单的从源点开始做bfs,并不断修改这条路上的delta量,直到找到源点或者找不到增广路。

    EK算法《例题POJ 1273》

    #include<iostream>
    #include<queue>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>  
    #define LL long long  
    #define s(a) scanf("%d",&a)
    #define scanf scanf_s
    const int inf = 0x3f3f3f;
    using namespace std;
    const int N = 205;
    int n, m, u, v, cost;
    int Map[N][N], path[N], flow[N];
    int start, endd;
    queue<int>q;
    int bfs(){
    	while (!q.empty()) q.pop();
    	memset(path, -1, sizeof(path));
    	path[start] = 0, flow[start] = inf;
    	q.push(start);
    	while (!q.empty()) {
    		int t = q.front();
    		q.pop();
    		if (t == endd) break;
    		for (int i = 1; i <= m; i++) {
    			if (i != start && path[i] == -1 && Map[t][i]) {
    				flow[i] = flow[t]<Map[t][i] ? flow[t] : Map[t][i];
    				q.push(i);
    				path[i] = t;
    			}
    		}
    	}
    	if (path[endd] == -1) return -1;
    	return flow[endd];
    }
    int Edmonds_Karp(){
    	int max_flow = 0, step, now, pre;
    	while ((step = bfs()) != -1) {
    		max_flow += step;
    		now = endd;
    		while (now != start) {
    			pre = path[now];
    			Map[pre][now] -= step;
    			Map[now][pre] += step;
    			now = pre;
    		}
    	}
    	return max_flow;
    }
    int main(){
    	while (EOF!=scanf("%d%d", &n, &m)) {
    		memset(Map, 0, sizeof(Map));
    		for (int i = 0; i<n; i++) {
    			scanf("%d%d%d", &u, &v, &cost);
    			Map[u][v] += cost;
    		}
    		start = 1, endd = m;
    		printf("%d\n", Edmonds_Karp());
    	}
    	return 0;
    }


    展开全文
  • 最大网络流的增广路算法,求最大流有一种经典的算法
  • 最短增广路算法(SAP) 最短增广路算法(SAP) 最短增广路算法(SAP) 最短增广路算法(SAP) 最短增广路算法(SAP)
  • 最短增广路算法(SAP): 1.初始化容量网络和网络流; 2.构造残留网络和层次网络,如果汇点不在层次网络中,则算法结束; 3.在层次网络中不断用BFS增广,直到层次网络中没有增广路为止;每次增广完毕,在层次网络...

    最短增广路算法(SAP):

    1.初始化容量网络和网络流;

    2.构造残留网络和层次网络,如果汇点不在层次网络中,则算法结束;

    3.在层次网络中不断用BFS增广,直到层次网络中没有增广路为止;每次增广完毕,在层次网络中要去掉因改进流量而导致饱和的弧;

    4.转到步骤(2)。

     

    连续最短增广路算法(Dinic):

    1.初始化容量网络和网络流;

    2.构造残留网络和层次网络,如果汇点不在层次网络中,则算法结束;

    3.在层次网络中用一次DFS过程进行增广,DFS执行完毕,该阶段的增广也执行完毕;

    4.转到步骤(2)。

    转载于:https://www.cnblogs.com/zufezzt/p/4637180.html

    展开全文
  • 该算法就是不断在残余网络中寻找增广路并增广,直到找不到增广路为止(也就是说,此时源点和汇点不连通,存在割)。下面给出增广路和增广的含义。 算法实现 const  maxn=200; var  c:array[1..maxn,1..maxn] of ...

    无题目

    该算法就是不断在残余网络中寻找增广路增广,直到找不到增广路为止(也就是说,此时源点和汇点不连通,存在割)。下面给出增广路和增广的含义。

    算法实现

    const

     maxn=200;

    var

     c:array[1..maxn,1..maxn] of longint;

     b:array[1..maxn] of longint;

     sum,s,t,n,m:longint;

     

    function min(a,b:longint):longint;

    begin

       if a>b then exit(b) else exit(a);

    end;

     

    function findflow(k:longint):boolean;

    var

     i:longint;

    begin

      if k=t then exit(true);

      for i:=1 to n do

       if (b[i]=-1) and (c[k,i]>0)

         then begin

                b[i]:=k;

                if findflow(i) then exit(true);

              end;

     exit(false);

    end;

     

    procedure addflow;

    var

     i,d:longint;

    begin

     d:=maxlongint;

     i:=t;

     while b[i]<>0 do

       begin

         if c[b[i],i]>0 then d:=min(d,c[b[i],i]);

         i:=b[i];

       end;

     i:=t;

     while b[i]<>0 do

       begin

         dec(c[b[i],i],d);

         inc(c[i,b[i]],d);

         i:=b[i];

       end;

     inc(sum,d);

    end;

     

    procedure init;

    var

     i,x,y,w:longint;

    begin

     readln(m,n);

     s:=1;t:=n;

      for i:=1 to m do

       begin

          readln(x,y,w);

          inc(c[x,y],w);

       end;

    end;

     

    procedure main;

    var

     i,j:Longint;

    begin

      for i:=1 to n do b[i]:=-1;

     b[s]:=0;

      whilefindflow(s) do

        begin

          addflow;

          for i:=1 to n do b[i]:=-1;

          b[s]:=0;

        end;

    end;

     

    procedure print;

    var

     i,j:longint;

    begin

     writeln(sum);

    end;

     

    begin

      init;

      main;

      print;

    end.


    展开全文
  • 二分图前期基础之增广路

    千次阅读 多人点赞 2018-05-02 00:31:53
    二分图前期基础之增广路 刚开始学习的时候,总是受困于增广路径,不明白增广路径是如何应用以及其具体的含义是什么,感谢博客https://www.cnblogs.com/logosG/p/logos.html 为了充分表达敬意,放在了文首 QAQ 晕了几...
  • 增广路算法求解最大流问题。 每一次找到一条从源点到汇点的不包含0流量的路径为一条增广路。 从s出发不断找增广路的过程,通过BFS想周围搜索与s直接相连的剩余流量不为0的结点,加入队列,每次从队列中取出一个元素...
  • 根据增广路地理,为了得到最大流,可以从任何一个可行流开始,沿着增广路对网络流进行增广,直到网络中不存在增广路为止,这样的算法称为增广路算法。 增广路算法流程如下。 (1)取一个可行流f作为初始流(如果没有...
  • 学习hopcroft-karp算法时看到这样一段对增广路的证明,想到之前学习匈牙利算法的时候也纠结过一阵子对增广路的证明,后来就不了了之。现在看到了,特意附上笔记。先上原文,节选自hopcroft-karp的wiki解释:...
  • 最大流增广路算法

    千次阅读 2013-02-21 18:27:00
    增广路方法   Augmenting path method (Ford Fulkerson method) 一般增广路算法   Labeling algorithm O(nmU) 在残留网络中,每次任意找一条增广路径增广。 容量缩放增广路算法   Capacity scaling ...
  • 网络流 增广路 回退

    2018-09-01 00:50:00
    增广路: 有流量标记: 流量变化: 转载于:https://www.cnblogs.com/cmyg/p/9568904.html
  • 增广路定理:我们用未盖点来表示不与任何匹配边邻接的点,其他点为匹配点,即恰好和一条匹配边邻接的点。从未盖点出发,依次经过非匹配边,匹配边,非匹配边,匹配边……所得到的路称为交替路。如果交替路的终点是一...
  • 线性规划网络流之最短增广路算法 代码实现 /* 最短增广路C++实现 参考资料:《趣学算法》陈小玉 人民邮电出版社 */ #include<iostream> #include<queue> #include<cstring> using namespace std; ...
  • 网络流——最大流增广路算法

    千次阅读 2017-08-14 21:29:03
    网络流——最大流增广路算法
  • 增广路求网路最大流

    2013-06-22 16:03:35
    /* 算法竞赛入门经典 增广路求网路最大流 * */ import java.util.Arrays; import java.util.LinkedList; import java.util.Scanner; public class MaxFlow { public static void main(String[] args) { ...
  • 基于增广路的网络流算法

    千次阅读 2013-12-14 20:02:08
    网络流算法由3大系组成,分别为增广路系,预留推进系,最小割系。下面介绍一下增广路系的网络流算法。 1.ek算法  网络流中基础算法,算法思想是每次用bfs找增广路。 2.dinic算法   理论时间复杂度为O(n^2m),...
  • 给出一个求解该问题的最大利润增广路算法,该算法能快速有效地求得该问题的最优解及目标函数值。用示例对算法的求解过程进行了演示,结果表明该算法比一般的线性规划方法更加的方便,且直观得多。
  • 网络流————Edmonds-Karp 最短增广路算法  ■求最大流的过程,就是不断找到一条源到汇的路径,然后构建残余网络,再在残余网络上寻找新的路径,使总流量增加,然后形成新的残余网络,再寻找新路径…..直到某个...
  • 网络流增广路(无费用)模板
  • 附录I 增广路中称为关键边的次数 在残余网络中,如果一条增广路径上的可增广量是该路径上边(u,v)的残余容量,则称边(u,v)为增广路径上的关键边。 如图I-1所示,一条可增广路径P: 1—2—4—6,这条增广路径...
  • 首先我们应该寻找增广路,对于寻找一条增广路,我们可以这样做: 第一步:我们首先通过广度搜索或者深度搜索来求出这个图的其中一条路径。并用Pre数组记录前驱。 第二步:我们可以通过求出此路径的残...
  • 网络流最大流问题-1(增广路——EK)

    千次阅读 2016-07-15 19:41:19
    增广路* 增广路定义:在残量网络中的一条从s通往t的路径,其中任意一条弧(u,v),都有其残量网络流量r[u,v]>0。 其中绿色的就是增广路增广路算法* 增广路算法:每次用BFS找一条最短的增广路径,然后沿着这条...
  • 一直对增广路这种贪心思想表示怀疑,今天看到一个很好的证明~首先介绍割的概念,所谓图的割,指的是某个顶点集合S属于V,从S出发的所有边的集合成为割(S,V\S),这些边的容量和被称为割的容量,如果有源点s属于S,汇点...
  • 网络流问题 网络流是一类关于图中(一般是有向图)的的流的问题。...增广路算法是用来求解最大流问题的算法,算法的思想就是:从0开始不断寻找增广路,然后反向增加流量,最终不能增加流量是停止算法 ...
  • SAP基本思路:准备好两个数组 vis[i]和pre[i], 1)vis[i]用来标记节点i是否被访问过,2)pre[i]用来记录节点i的前驱节点,(用来记录发现的增广路)准备好两个数组g[i][j]和map[i][j], 1)g[i][j]代表残余网络,残余...
  • 增广路求最大流:EK算法详解

    千次阅读 2018-05-06 15:40:24
    算法简介:EK算法,全称Edmonds-Karp算法。我个人认为学习一个新算法...我这个版本用BFS找增广路(当然也可以用DFS,但是时间复杂度......),存图用邻接表。不会BFS和邻接表的同学请......------------------------...
  • EK算法的思路非常的简单,就是一直找增广路径(BFS),假如有,记录增广路的最小值k,ans +=k ,并更新网络的值(要用反向边)。 贴模板: #include&amp;amp;lt;iostream&amp;amp;gt; #include&amp;...
  • 网络流DINIC增广路算法  【算法讲解】:首先构图,将节点间的容量和流量记录下。接下来,构建层次图,然后进行DINIC网络流算法,递归求增广路,只是更新的时候要判断是否初始点的d值+1等于到达点  【题目】:POJ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 28,991
精华内容 11,596
关键字:

增广路