精华内容
下载资源
问答
  • 最大流

    千次阅读 2015-12-26 18:44:40
    维护一个残存网络(存储分配后每条边剩余的容量),初始为最大容量。(在以下代码中,没有特别开一个数组存储残存网络,而是通过原容量减去网络得到残存网络)  通过在残存网络里寻找增广
    

    ▶ 问题 

    在一个有向图里,每个路径都有最大容量,通过这个图最多能运输多少货物。默认容量非负,且不能同时存在边(uv)和(vu)。 

    ▶ 基本思路 

    维护一个流网络,初始化为0,不断增加流的值。 

    维护一个残存网络(存储分配流后每条边剩余的容量),初始为最大容量。(在以下代码中,没有特别开一个数组存储残存网络,而是通过原容量减去流网络得到残存网络 

    通过在残存网络里寻找增广路径(残存网络中从一条从源结点s到汇结点t的简单路径),并且根据这条路径的残存容量(能够为每条边增加的流量的最大值,也就是这条路径经过边的最小容量)来更新残存网络和流网络(在流网络里加上这个值,在残存网络里减去这个值),直到在残存网络中找不到增广路径为止。 

    在找不到增广路径时,流达到了稳定状态,也就是横跨任何切割的净流量相同,这个净割线的边流量的和为净流量,注意正向相加,反向相减 

    ▶ 代码实现 

    ·基本变量 

      int cap[MAX][MAX];  //记录每条路径的最大容量

      int flow[MAX][MAX];  //记录当前的流网络

      int a[MAX];    //记录当前路径的残存容量(最终的残余容量存储在a[t]中)

    int path[MAX];   //路径压缩

    int ans=0;    //存储最大流 

    memset(cap,0,sizeof(cap));

    memset(flow,0,sizeof(flow));

    s代表源结点下标,t代表汇结点下标 

      以下过程循环进行,直到残存网络不包括任何增广路径:

    ·循环结束条件

     

    a[t]==0 ,其中t代表汇结点,残余容量仍旧是初始值0,说明残余容量数据没有更新到汇结点处,也就说明找不到增广路径。 

    if(a[t]==0) break;

     

    ·循环具体步骤

     

    ①利用宽度优先搜索,在残存网络里找到一条增广路径。 

    queue<int>q;  //全局变量,bfs使用 

    memset(a,0,sizeof(a));  

    a[s]=INF;   // 3,4行操作对象是源结点,s代表源结点的下标值

    q.push(s);

    while( !q.empty() ){

        u=q.front();q.pop();

        for(v=0;v<n;v++){

        if( !a[v] && cap[u][v]>flow[u][v]){

        path[v] = u;

    q.push(v);

    a[v] = min(a[u],cap[u][v]-flow[u][v]); 

            }

        }

    } 

    ②更新流网络 

    for(u=t;u!=s;u=path[u]){

        flow[path[u]][u]+=a[t];

        flow[u][path[u]]-=a[t];

    }

    ③用当前路径残存容量更新最大流 

    ans+=a[t];

      

    ▶ 示例 

      橙色路径为当前的增广路径,图里显示的是残存网络

    第一轮循环:

    残存容量:12ans = 12

    第二轮循环:

    残存容量:4ans = 16

    第三轮循环:

    残存容量:7ans = 23

     

    找不到增广路径

    最终最大流为23

     

    此时的稳定流网络:

     

    检测各个切割:

       

       净流量12+11 = 23                                         净流量 12+7+4 = 23

     

         

       净流量11+19-7 = 23                                     净流量19+4 = 23

     

     

    ▶ 具有多个源结点和汇点的网络

     

    构造一个超级源结点和超级源汇点,让超级源结点指向所有源结点,添加一条容量为正无穷的有向边;让所有源汇点指向超级源汇点,添加一条容量为正无穷的有向边。

    其余和普通最大流问题解决方法相同。

     

     

    *《算法导论》中给出了存在反平行边的处理办法

    *这里未引入反向边的概念,《算法导论》中的反向边就是这里的流网络。

    展开全文
  • 最大流问题

    千次阅读 2016-09-06 16:45:15
    举例描述最大流问题是一个很经典的问题,很多人对此也很熟悉,它能够等同于一个线性规划问题。下面给出最大流问题的一个基本描述:如下图所示,s是源点,t为汇点,每条边上数字的含义是边能够允许流过的最大流量。...

    举例描述

    最大流问题是一个很经典的问题,很多人对此也很熟悉,它能够等同于一个线性规划问题。下面给出最大流问题的一个基本描述:如下图所示,s是源点,t为汇点,每条边上数字的含义是边能够允许流过的最大流量。可以将边看成管道,0/3代表该管道每秒最多能通过3个单位的流量,0代表当前流量。最大流问题即是说,从s点到t点,最大允许流量是多少?

    这里写图片描述

    公式描述

    这里写图片描述
    的流量等于流出该点的流量。这个可以理解为流量守恒,就如同电流一样,流入一个电阻的电流必然等于流出的电流。

    那么最大流就可以表示为:
    这里写图片描述

    Ford-Fulkerson解法介绍

    该方法依赖于三种重要思想:残留网络,增广路径和割

    Ford-Fulkerson思想

    Ford-Fulkerson是一种迭代的方法。开始时,对所有的u,v属于V,f(u,v)=0(这里f(u,v)代表u到v的边当前流量),即初始状态时流的值为0。在每次迭代中,可以通过寻找一个“增广路径”来增加流值。增广路径可以看做是从源点s到汇点t之间的一条路径,沿该路径可以压入更多的流,从而增加流的值。反复进行这一过程,直到增广路径都被找出为止。

    增广路径

    举个例子来说明下,如图所示,每条红线就代表了一条增广路径,当前s到t的流量为3。当然这并不是该网络的最大流,根据寻找增广路径的算法我们其实还可以继续寻找增广路径。

    这里写图片描述

    残留网络

    顾名思义,残留网络是指给定网络和一个流,其对应还可以容纳的流组成的网络。具体说来,就是假定一个网络G=(V,E),其源点s,汇点t。设f为G中的一个流,对应顶点u到顶点v的流。在不超过C(u,v)的条件下(C代表边容量),从u到v之间可以压入的额外网络流量,就是边(u,v)的残余容量(residual capacity),定义如下:

    r(u,v)=c(u,v)-f(u,v)

    举个例子,假设(u,v)当前流量为3/4,那么就是说c(u,v)=4,f(u,v)=3,那么r(u,v)=1。

    我们知道,在网络流中还有这么一条规律。从u到v已经有了3个单位流量,那么从反方向上看,也就是从v到u就有了3个单位的残留网络,这时r(v,u)=3。可以这样理解,从u到v有3个单位流量,那么从v到u就有了将这3个单位流量的压回去的能力。

    我们来具体看一个例子,如下图所示一个流网络

    这里写图片描述

    对应的残留网络:

    这里写图片描述

    求解步骤举例

    1.获得残留网络

    2.穷举所有的增广路径

    如下图所示:

    这里写图片描述

    计算最大流的标号法

    这里介绍计算网络最大流的简便方法—标号法,此方法是Ford—Fulkerson 于1956年提出来的,它的原理是利用寻找增广链来不断改善可行流。
    设μ是网络中 到 的一条链,规定 到 的方向为μ的方向。 μ上与μ的方向一致的弧称为前向弧,前向弧的集合记为μ+, μ上与μ的方向相反的弧称为后向弧,后向弧的集合记为μ-。

    这里写图片描述
    上图
    若给一个可行流{},称网络中 = 的弧为饱和弧,称 <的弧为非饱和弧,称 =0的弧为零流弧,称 >0的弧为非零流弧。
    增广链:设{}是可行流, μ是 到 的一条链,若μ满足下列条件,则称μ为关于 f 的增广链。(注意: f ={})
    1°对于任何( ,)∈μ+,0≤ < (前向弧为非饱和弧)
    2°对于任何( ,)∈μ-,0 <≤ (后向弧为非零流弧)

    博客参考:

    smartxxyx的两篇博客:
    http://blog.csdn.net/smartxxyx/article/details/9275177
    http://blog.csdn.net/smartxxyx/article/details/9293665/
    以及:
    http://dec3.jlu.edu.cn/webcourse/t000048/yun/ch7_04.htm

    展开全文
  • 最大流应用实验

    千次阅读 2019-07-06 14:24:35
    最大流应用问题 实验概述 论文评审问题 有m篇论文和n个评审,每篇论文需要安排a个评审,每个评审最多评b篇论文。请设计一个论文分配方案。 要求应用最大流解决上述问题,画出m=10,n=3的流网络图并解释说明流网络图...

    最大流应用问题

    实验概述

    论文评审问题

    1. 有m篇论文和n个评审,每篇论文需要安排a个评审,每个评审最多评b篇论文。请设计一个论文分配方案。
    2. 要求应用最大流解决上述问题,画出m=10,n=3的流网络图并解释说明流网络图与论文评审问题的关系。
    3. 编程实现所设计算法,计算a和b取不同值情况下的分配方案,如果没有可行方案则输出无解。

    实验思路

    最大流建图

    论文-评委是一个二分图,讨论的是二分图的连接问题。以流量的角度来看,我们向每篇论文发放一个容量为a的流量。而评委方每个评委可以承载的流量为b。最后,我们需要将论文方的流量全部发送到评委方。如果流量没有全部发送完毕,就是一个无解的情况。为了使用最大流的算法,可以在论文方添加一个源点,评委方添加一个汇点。
    origin
    源点可以看作是发送站,要将a流量发至每一个论文结点。然后论文结点需要想办法将流量发至评委结点,而每个论文结点和评委结点之间都有一条路,其容量为1,既代表评审一篇论文。专家结点要想办法将流量发送到汇点,因为那样才能完成一篇论文的评审。每个专家与汇点的通路的容量为b,既每个专家最多评审b篇论文。b用完后,该专家无法到达汇点(无法完成论文评审)。

    最大流求可行解

    我们知道最大流问题是求源点到汇点送出的流的最大值。在本问题中,要想把所有论文评审完毕,最大流就必须是m*a。
    remain
    最后找到所有从评委到论文的边,这些边都是原来论文到评委的反向边,代表经过了这些路径。

    画出的反向边就是最后的连线

    如果最后发现最大流 < m*a,就没有解,因为源点送出去的流量没有全部传到。本质上是有论文没有被审批。造成这种现象的原因是论文必须要a个评委,而评委有上限为b篇论文。在网络中,体现为评委向汇点的路径不能承受所有传递过来的流量。
    final
    标出的红色边是未送达的流量,说明无解

    直接判断有无解的方法就是看是否am < bn && a < n。如果是就一定有解,既评委向汇点的路径必能承受所有传递来的流量。
    no-sol

    最大流算法

    现在,问题基本上就解决了,我们可以使用最大流算法来求解了。最大流算法五花八门,大家可以自行百度。其中《算法导论》中的例子是Ford Fulkson (DFS),更好的是EK (Edmons-Karp)算法 (BFS),但不是最好。最好的算法是Dinic,一种BFS分层DFS方法,因为我们的二分图具有明显的层次感。我们老师的要求是比较EK和Dinic,当然最好是多实现几种最大流算法啦。

    展开全文
  • 最大流算法

    千次阅读 多人点赞 2019-08-22 18:04:13
    最大流算法 网络流基础概念 网络流 在一个有向图G=(V,E)G= (V,E)G=(V,E)中: 有一个唯一的源点S(入度为000:出发点) 有一个唯一的汇点T(出度为000:结束点) 图中的每一条边都一个非负的权值,这个权值叫做容量c(u,v...

    最大流算法

    网络流基础概念

    网络流

    在一个有向图 G = ( V , E ) G= (V,E) G=(V,E)中:

    • 有一个唯一的源点S(入度为 0 0 0:出发点)
    • 有一个唯一的汇点T(出度为 0 0 0:结束点)
    • 图中的每一条边都一个非负的权值,这个权值叫做容量 c ( u , v ) c(u, v) c(u,v)

    满足上述条件的图 G G G称为网络流图,记为 G = ( V , E , C ) G= (V,E,C) G=(V,E,C)

    可以想象成,如果把每条边都看成一个管道,可以看成是水从源点S出发经过这些管道,最终流向汇点T,而每条管道有最大的容量。

    例如

    可行流

    流量:每条弧上给定一个实数 f ( u , v ) f(u,v) f(u,v),满足 0 ≤ f ( u , v ) ≤ c ( u , v ) 0 \leq f(u,v) \leq c(u,v) 0f(u,v)c(u,v)

    可行流满足:

    • 源点S:流出量 = 整个网络的流量
    • 汇点T:流入量 = 整个网络的流量
    • 中间的点:总流入量 = 总流出量,同时 0 ≤ f ( u , v ) ≤ c ( u , v ) 0 \leq f(u,v) \leq c(u,v) 0f(u,v)c(u,v)

    这样的在整个网络中的流量就是可行流,可行流有多个

    例如

    红色的部分表示流量,黑色的表示容量。可行流就是7

    最大流

    • 所有可行流中流量最大的流量
    • 最大流可能不止一个

    最大流为11

    求解最大流算法

    反向边

    • 首先要明白一点,在一条从 S S S T T T的路径中,能够带来的最大流量取决于这条路径上的最小容量。

    对于下面这张图 1 1 1是源点, 4 4 4是汇点

    如果我们使用搜索算法找一条从1到4的路径,并且这条路径能够带来的流量是这条路径上边的容量的最小值,

    假设我们找到的路径是 1 − &gt; 2 − &gt; 3 − &gt; 4 1-&gt;2-&gt;3-&gt;4 1>2>3>4,现在的流量是 1 1 1,因为这条路已经使用过了,把这条路径上的每条边减 1 1 1,再次找从1到4的路径,发现找不到了,因此得到的答案为1,但是正确的答案应该是 2 2 2。即 1 − &gt; 2 − &gt; 4 1-&gt;2-&gt;4 1>2>4 1 − &gt; 3 − &gt; 4 1-&gt;3-&gt;4 1>3>4

    这个时候,为了能够继续找到路径,必须要反向建立边,把当前路径反向建边,边的权值就是这条路径的流量

    如图

    其中红色的边就是反向建立的,这个时候继续寻找一条路径,发现可以走 1 − &gt; 3 − &gt; 2 − &gt; 4 1-&gt;3-&gt;2-&gt;4 1>3>2>4,带来的流量是 1 1 1,然后继续找寻路径,发现没有可达的路径了,因此最大流是 1 + 1 = 2 1+1=2 1+1=2

    为什么要反向建边呢,仔细想想应该能够明白,反向建立边的作用相当于让之前的路径有可以反悔的余地。这样即使一开始走错也没有关系,因为可以通过反向边来反悔,最终一定能得到正确答案

    增广路经

    明白了反向建边后,来看什么是增广路经?

    如果一个可行流不是最大流,那么当前网络中一定存在一条增广路经。

    从源点 S S S到汇点 T T T的一条路径中,如果边 ( u , v ) (u,v) (u,v)与该路径的方向一致就称为正向边,否则就记为逆向边,如果在这条路径上的所有边满足

    • 正向边 f ( u , v ) &lt; c ( u , v ) f(u,v) &lt;c(u,v) f(u,v)<c(u,v)
    • 逆向边 f ( u , v ) &gt; 0 f(u, v) &gt; 0 f(u,v)>0

    则该路径是增广路径

    其实增广路径就是通过这样一条路径,来增加到达汇点的流量,而路径中的流量没到达容量。

    (在上图中,其实每次找到的一条从 1 1 1 4 4 4的路径都是一条增广路径)

    沿这条增广路改进可行流的操作称为增广.所有可能的增广路径放在一起就构成了残余网络

    以下这 2 2 2个算法,都是基于不断找增广路经来实现的

    EK算法

    复杂度 O ( n m 2 ) O(nm^2) O(nm2) n n n是点数, m m m是边数

    首先要考虑的是怎么找增广路径,之前说用搜索算法,可以用 b f s bfs bfs也可以用 d f s dfs dfs,但是 b f s bfs bfs的好处在于能够在残余网络中每一次找到最短的一条增广路径。因此在 E K EK EK算法是基于 b f s bfs bfs来找增广路经, b f s bfs bfs每执行一次,就找出一条增广路径来,然后把这条路径上的权值进行修改,同时反向建边。直到找不到增广路径为止,算法就结束了(代码注释写的很详细)

    步骤

    • 利用 b f s bfs bfs找到一条最短增广路径,记录该路径的最小流量
    • 利用一个数组把这个路径上的流量更新
    • 不断重复 1 , 2 1,2 1,2直到没有增广路径为止

    具体实现:

    POJ 1273(模板题)题目链接

    代码

    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <queue>
    #define N 205
    #define INF 0x7fffffff
    #define ll long long
    ll min(ll a, ll b) {
    	return a > b ? b : a;
    }
    using namespace std;
    // Ek 找最大流,其中源点是1,汇点是n
    ll g[N][N], pre[N], dis[N]; //g用来存图,pre[i]表示当前节点i的前一个节点,dis[i]表示从源点到i点的路径上的最小流量
    ll n, m, s, t, ans;
    queue <ll> q; 
    
    ll bfs () { //找到一条增广路经, 返回这条路径的流量
    	for(int i = 1; i <= n; i++) pre[i] = -1;
    	while(!q.empty()) q.pop();
    	q.push(s);
    	dis[s] = INF;
    	while (!q.empty()) {
    		ll x = q.front();
    		q.pop();
    		if(x == t) break; //找到了汇点
    		for(int i = 1; i <= n; i++) {
    			if(pre[i] == -1 && g[x][i]) { //找到一个没有被访问且还有容量的点
    				pre[i] = x;
    				dis[i] = min(dis[x], g[x][i]); //更新增广路径上的最小流量
    				q.push(i);
    			}
    		}
    	}
    	if(pre[t] == -1) return -1; //说明没有增广路径了,因此才走不到汇点
    	else return dis[t];
    }
    
    void EK () { //更新残余网络的流量
    	ll inc;
    	while (1) {
    		inc = bfs();
    		if(inc == -1) break; //没有增广路径了,算法结束
    		ll k = t;
    		while (k != s) {
    			g[k][pre[k]] += inc; //建立反向弧
    			g[pre[k]][k] -= inc; //正向容量减去流量
    			k = pre[k];
    		}
    		ans += inc;
    	}
    }
    
    int main () {
    	ll u, v, cost;
    	while(scanf("%lld %lld", &m, &n) != EOF) { //读入数据,记得初始化
    		memset(dis, 0, sizeof(dis));
    		memset(g, 0, sizeof(g));
    		ans = 0;
    		s = 1, t = n;
    		for(int i = 1; i <= m; i++) {
    			scanf("%lld %lld %lld", &u, &v, &cost);
    			g[u][v] += cost;
    		}
    		EK();
    		printf("%lld\n", ans);
    	}
    	return 0;
    }
    

    Dinic算法

    复杂度 O ( V 2 E ) O(V^2E) O(V2E)

    E K EK EK算法找增广路径是基于 b f s bfs bfs来进行的, b f s bfs bfs会把周围能够扩展的点全部扩展进来,直到找到汇点为止,相当于每找一次增广路径都要搜索大量的点。 D i n i c Dinic Dinic算法实际上是对 E K EK EK的优化

    D i n i c Dinic Dinic算法利用 b f s bfs bfs建立分层网络 (所谓分层网络,就是按照每一个点到源点的距离,分层,方便后面的 d f s dfs dfs)。然后基于这个分层网络,使用 d f s dfs dfs找到当前分层网络下的所有增广路径,并且做好相应的修改。然后不断重复这两个过程,直到无法分层为止,这样做只需要一次 b f s bfs bfs就可以找到多条增广路径。

    (PS:分层网络,就是利用 b f s bfs bfs特性,源点为起点,一直扩散出去,每一个点都打一个标记,标记到源点的路径所经过的最少的弧的数量,假设用 d i s [ i ] dis[i] dis[i]表示 i i i到源点S的最少经过的弧的数量,这样就可以将整个网络分层,基于这个分层网络, d f s dfs dfs找增广路径的时候,就可以找到最短的增广路径。如果当前点是 x x x d f s dfs dfs搜到下一个点 i i i,一定要满足 d i s [ i ] = d i s [ x ] + 1 dis[i] = dis[x] +1 dis[i]=dis[x]+1,这样才是最短增广路径,效率才是最高的。)

    步骤

    • 利用 b f s bfs bfs建立分层网络(记录每个节点的深度)
    • 按照当前分层网络进行 d f s dfs dfs(一层一层找),找到所有该分层网络下的增广路径,并更新残余网络
    • 重复 1 、 2 1、2 12直到无法建立分层网络为止

    邻接矩阵实现

    POJ 1273(模板题)题目链接

    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <queue>
    #define N 205
    #define INF 0x7fffffff
    #define min(a,b) a>b?b:a
    using namespace std;
    
    int n, m, s, t, maxflow;
    int deep[N], g[N][N]; // deep 表示从源点到当前节点的深度
    queue <int> q;
    
    bool bfs () { //建立分层网络
    	while(!q.empty()) q.pop();
    	memset(deep, -1, sizeof(deep));
    	deep[s] = 0; // 源点的深度为0
    	q.push(s);
    	while(!q.empty()) {
    		int x = q.front();
    		q.pop();
    		for(int i = 1; i <= n; i++) {
    			if(g[x][i] > 0 && deep[i] == -1) {// 如果有容量能够到达i,并且i节点的深度未被标记
    				deep[i] = deep[x] + 1;
    				q.push(i);
    			}
    		}
    	}
    	if(deep[n] > 0) return true; //能够建立分层图
    	else return false; //不存在分层网络时,算法结束
    }
    
    //基于当前分层图,找到所有增广路径
    int dfs (int x, int mx) { //表示当前节点x,以及这条增广路经上的最小流量
    	int a;
    	if(x == t) return mx;
    	for(int i = 1; i <= n; i++) {
    		if( g[x][i] > 0 && deep[i] == deep[x] + 1 && (a = dfs(i, min(mx, g[x][i]))) ) {//找到x能流通过去的的相邻顶点i
    			g[x][i] -= a; //更新残余网络
    			g[i][x] += a;
    			return a;
    		}
    	}
    	return 0;
    }
    
    void dinic () {
    	while(bfs())
    		maxflow += dfs(s, INF);
    }
    
    int main () {
    	int u, v, cost;
    	while(scanf("%d %d", &m, &n) != EOF) {
    		s = 1, t = n;
    		memset(g, 0, sizeof(g));
    		maxflow = 0;
    		for(int i = 1; i <= m; i++) {
    			scanf("%d %d %d", &u, &v, &cost);
    			g[u][v] += cost;
    		}
    		dinic();
    		printf("%d\n", maxflow);
    	}
    	return 0;
    }
    

    链式前向星实现(内存小)

    其中需要注意的细节:

    • 存边的时候反边的容量设置为0;

    • 假设 d f s dfs dfs在递归回来的时候找到了这条增广路径的流量为 f l o w flow flow,需要更新正反边

      • 正边: e d g e [ i ] . c a p &ThinSpace;&ThinSpace;&ThinSpace;&ThinSpace; − = &ThinSpace;&ThinSpace;&ThinSpace;&ThinSpace; f l o w edge[i].cap \,\,\,\,-= \,\,\,\,flow edge[i].cap=flow
      • 反边: e d g e [ i ^ 1 ] . c a p &ThinSpace;&ThinSpace;&ThinSpace;&ThinSpace; + = &ThinSpace;&ThinSpace;&ThinSpace;&ThinSpace; f l o w edge[i \hat{} 1].cap\,\,\,\, +=\,\,\,\, flow edge[i^1].cap+=flow
      • 其中 ^ \hat{} ^表示按位异或,如果 i i i是偶数则 i ^ 1 = i + 1 i \hat{} 1 = i+1 i^1=i+1,如果 i i i是奇数则 i ^ 1 = i − 1 i \hat{} 1 = i -1 i^1=i1,为什么反边就是 i ^ 1 i \hat{} 1 i^1呢。因此在存边的时候,是先存的正边,然后 + + c n t ++cnt ++cnt后存反边,正反边差 1 1 1个,为了保证正边的编号是偶数,反边是奇数, c n t cnt cnt初始化为 − 1 -1 1(因为我的习惯是写 + + c n t ++cnt ++cnt

    洛谷 网络最大流题目链接

    #include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <queue>
    #define INF 0x7fffffff
    #define N 10001
    #define M 100005
    using namespace std;
    
    struct flow {
    	int to, next, cap;
    }edge[M * 4];
    
    int n, m, s, t, maxflow;
    int cnt = -1;
    int head[N], dep[N]; //其中dep[i]表示i的深度,也就是到源点的最小边数	
    queue <int> q;
    inline void addEdge (int u, int v, int cost) {
    	edge[++cnt].to = v;
    	edge[cnt].cap = cost;
    	edge[cnt].next = head[u];
    	head[u] = cnt;
    	//反向建边,容量为0
    	edge[++cnt].to = u;
    	edge[cnt].cap = 0;
    	edge[cnt].next = head[v];
    	head[v] = cnt;
    }
    
    bool bfs () { //建立分层网络
    	while(!q.empty()) q.pop();
    	memset(dep, -1, sizeof(dep));
    	dep[s] = 0;
    	q.push(s);
    	while(!q.empty()) {
    		int x = q.front(); q.pop();
    		for(int i = head[x]; i != -1; i = edge[i].next) {
    			int u = edge[i].to;
    			int cap = edge[i].cap;
    			if(cap > 0 && dep[u] == -1) {
    				dep[u] = dep[x] + 1;
    				q.push(u);
    			}
    		}
    	}
    	if(dep[t] == -1) return 0;
    	else return 1;
    }
    
    int dfs (int x, int mx) { 
    	int a;
    	if(x == t) return mx; //找到汇点,返回
    	for(int i = head[x]; i != -1; i = edge[i].next) {
    		int u = edge[i].to;
    		int cap = edge[i].cap;
    		if(cap > 0 && dep[u] == dep[x] + 1 && (a = dfs(u, min(cap, mx))) ) {
    			edge[i].cap -= a; 
    			edge[i^1].cap += a; //反向边
    			return a;
    		}
    	}
    	return 0; //搜不到增广路经了就返回0
    } 
    
    void dinic () {
    	int res;
    	while ( bfs() )  //当前网络下,搜索所有的增广路径
    		while (1) {
    			res = dfs(s, INF); //加上该路径能带来的流量
    			if(!res) break;
    			maxflow += res;
    		}
    }
    
    int main () {
    	int u, v, cost;
    	memset(head, -1, sizeof(head));
    	scanf("%d %d %d %d", &n, &m, &s, &t);
    	for(int i = 1; i <= m; i++) {
    		scanf("%d %d %d", &u, &v, &cost);
    		addEdge(u, v, cost);
    	}
    	dinic();
    	printf("%d", maxflow);
    	return 0;
    }
    

    算法还可以优化,加入一个 c u r cur cur数组。

    首先要明白在 d f s dfs dfs找增广路径的时候,一定是完全增广的,也就是说这条路径使用过后,下一次不必再次检查这条路径了。直接从下一条边开使找,加入这个优化,算法能快不少

    int cur[N];
    bool bfs () {
    	while(!q.empty()) q.pop();
    	for(int i = 0; i <= n; i++) cur[i] = head[i]; //复制head数组
    	memset(dep, -1, sizeof(dep));
    	dep[s] = 0;
    	q.push(s);
    	while(!q.empty()) {
    		int x = q.front(); q.pop();
    		for(int i = head[x]; i != -1; i = edge[i].next) {
    			int u = edge[i].to;
    			int cap = edge[i].cap;
    			if(cap > 0 && dep[u] == -1) {
    				dep[u] = dep[x] + 1;
    				q.push(u);
    			}
    		}
    	}
    	if(dep[t] == -1) return 0;
    	else return 1;
    }
    int dfs (int x, int mx) {
    	int a;
    	if(x == t) return mx;
    	for(int i = cur[x]; i != -1; i = edge[i].next) {
    		cur[x] = i; //避免了搜寻已经增广过的路径
    		int u = edge[i].to;
    		int cap = edge[i].cap;
    		if(cap > 0 && dep[u] == dep[x] + 1 && (a = dfs(u, min(cap, mx))) ) {
    			edge[i].cap -= a;
    			edge[i^1].cap += a; //反向边
    			return a;
    		}
    	}
    	return 0; //搜不到增广路经了就返回0
    } 
    
    展开全文
  • 网络最大流

    万次阅读 2018-03-13 21:48:38
    如何求最大流 游戏现在开始 Dinic算法 我这个连kmp和rmq都不会的蒟蒻现在才勉强能看懂网络流. 唉. 关于网络流,基础知识很多博客上都有.让我也来扯会淡. 网络流是什么? 考虑以下情景. 假设我家非常有钱...
  • 图论--网络流最大流问题

    千次阅读 多人点赞 2019-10-28 21:21:05
    在介绍最大流问题的解决方法之前,先介绍几个概念. 网络:网络是一个有向带权图,包含一个源点和一个汇点,没有反向平行边。 网络流:网络流即网上的流,是定义在网络边集E上的一个非负函数flow={flow(u,v)}, ...
  • 上一篇中介绍了网络流的基础,最大流最小割定理的证明,下面来看如何求一个容量网络的最大流,这里介绍四种算法:EK算法、SAP算法、DINIC算法、HLPP算法。这四种算法中,前三种基于增广路,最后一种基于预流推进。 ...
  • 网络流(最大流)基础入门

    千次阅读 多人点赞 2017-07-11 09:45:39
    **定义 网络流与最大流**网络流是指给定一个有向图,和两个点–源点S和汇点T,点之间有连边, 每条边有一个容量限制,可以看作水管,网络流就是指由S点流到T点的一个可行流。 最大流就是指所有可行流里面最大的流...
  • 网络流——最大流增广路算法

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

    千次阅读 2016-05-17 15:20:50
    网络流的三个性质: 1、容量限制: f[u,v] 2、反对称性:f[u,v] = - f[v,u] ...最大流问题,就是求在满足网络流性质的情况下,源点 s 到汇点 t 的最大流量。 算法的关键在于 1)如何找出增广路径。 2)如何更新流
  • 最小费用最大流C++算法,有最小费用算法,最大流算法,最短路算法,C++代码。
  • 基于matlab的最大流最小费用代码 适于学习、修改、借鉴
  • 网络流问题:最大流及其算法

    万次阅读 多人点赞 2017-03-22 16:25:34
    首先要先清楚最大流的含义,就是说从源点到经过的所有路径的最终到达汇点的所有流量和。  流网络G=(V,E)是一个有向图,其中每条边(u,v)∈E均有一个非负容量c(u,v)>=0。如果(u,v)不属于E,则假定c(u,v)=0。流网络中...
  • Java实现最小费用最大流问题

    万次阅读 多人点赞 2019-07-26 17:48:33
    最大流有多组解时,给每条边在附上一个单位费用的量,问在满足最大流时的最小费用是多少? 2 解决方案 下面代码所使用的测试数据如下图: package com.liuzhen.practice; import java.util.ArrayList; import ...
  • 网络流之最大流和最小割

    千次阅读 2017-02-16 11:32:52
    最大流问题最大流:给定有向图中每条边的最大流量(容量),求从源点到汇点的最大流量。容量网络: 括号左边代表容量,右边代表流量。残留网络:流网络中剩余可增加的流量增广路:满足容量条件的一条流量不为零的路径...
  • dinic网络最大流

    千次阅读 2018-08-16 08:23:49
    网络流是什么? 不急我们慢慢来讲。 首先我们先看看最大流 ...管道网络中每条边的最大通过能力(容量)是有限的,实际流量...求最大流的标号算法最早由福特和福克逊与与1956年提出,20世纪50年代福特(Ford)、(Fulk...
  • 最大流的算法: Ford-Fulkerson算法  求最大流的过程,就是不断找到一条源到汇 的路径,然后构建残余网络,再在残余网络 上寻找新的路径,使总流量增加,然后形成 新的残余网络,再寻找新路径…..直到某个 残余...
  • 最大流算法 - 标号法

    千次阅读 多人点赞 2020-04-09 19:18:46
    标号法求最大流 相关概念 算法基本思想: 从某个初始流开始,重复地增加流的值到不能再改进为止,则最后所得的流将是一个最大流。为此,不妨将每条边上的流量设置为0作为初始流量。为了增加给定流量的值,我们必须找...
  • 网络流-最小费用最大流

    千次阅读 2016-07-12 15:40:27
    (在最小费用最大流中,最大流量是唯一的,但是最大流不唯一,在保证最大流的条件下,加上一些参数,确定最小费用最大流的唯一性) 最小费用流其实是线性规划的一种特殊类型。所以解决最小费用流的方式其实可以为...
  • 最大流——HLPP算法

    千次阅读 2017-03-08 21:27:26
    HLPP(最高标号预流推进)算法是最大流算法中最快的一种,经过一周多的研究,终于明白了...
  • 二分图最大匹配(最大流

    千次阅读 2019-07-27 16:42:27
    先举个例子,有N台计算机和K个任务,每个计算机只能执行一个任务,但可以执行多种任务。...看到这个图片大家肯定特别的熟悉,这不就转换为了我们的最大流问题了,权值只不过都是固定的1而已,其他的都是套模...
  • 最小费用最大流问题

    千次阅读 2019-06-23 02:28:00
    复杂网络中,单源单点的最小费用最大流算法(MCMF)应用广泛。  在实际网络问题中,不仅考虑从 Vs 到 Vt 的流量最大,还要考虑可行流在网络传送过程中的费用问题,这就是网络的最小费用最大流问题。  最小费用最大...
  • 最大流(Max Flow)

    千次阅读 2019-05-03 12:17:50
    最大流(Max Flow) 一、流网络 G=(V,E)是一个有向图,其中每条边(u,v)有一个非负的容量值c(u,v),而且如果E中包含一条边(u,v),那么图中就不存在它的反向边。在流网络中有两个特殊的结点,源结点s和...
  • 网络流的最大流入门(从普通算法到dinic优化)

    万次阅读 多人点赞 2018-01-26 23:57:47
    而我们今天要讲的就是网络流里的一种常见问题——最大流问题。 最大流问题(maximum flow problem),一种组合最优化问题,就是要讨论如何充分利用装置的能力,使得运输的流量最大,以取得最好的效果。求最大流的标号...
  • 最大流最小割算法入门理解

    万次阅读 多人点赞 2015-04-14 13:31:02
    最近在看maxflow相关的资料,本文主要介绍下自己对最大流和最小割的理解。最大流本来是网络流方面的算法,后来在计算机视觉中也得到广泛的应用,如图割。我觉得要理解一个算法首先要从起源开始,然后再去泛化问题、...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 790,971
精华内容 316,388
关键字:

最大流