当前位置：自学咖网 > 技术教程 > 编程最新 > Dinic算法理解
wenwen 编程最新

Dinic算法理解

【网络流】Dinic算法理解 [编程语言教程]

EK算法还是不够优秀，我们还是要学习更加优秀的Dinic算法才能解决更多要求较高的问题。

这里确保大家都是懂得网络流的一些基本概念的，如果不懂的，这里有一个链接，大家可以看一看。网络流详解（显然不是我写的！）

他的EK算法比我写的好看的多，强势给大家安利一波！！！

同时大家可以注意下这张图，结合链接中的讲解认真理解一下就可以懂得为什么要反向连边的原理！

就是给你一次反悔的机会，类似于我们搜索时改变当前层的一个变量，后面又要把他改回来！！！

技术图片

这里转载一下EK算法和Dinic算法的一些算法大体实现思想

一般增广路算法(EdmondsKarp)

在一般的增广路算法中, 程序的实现过程与增广路求最大流的过程基本一致. 即每一次更新都进行一次找增广路然后更新路径上的流量的过程。但是我们可以从上图中发现一个问题, 就是每次找到的增广路曲曲折折非常长, 此时我们往往走了冤枉路(即：明明我们可以从源点离汇点越走越进的，可是中间的几条边却向离汇点远的方向走了), 此时更新增广路的复杂度就会增加。EK 算法为了规避这个问题使用了 bfs 来寻找增广路, 然后在寻找增广路的时候总是向离汇点越来越近的方向去寻找下一个结点。

借用一下代码：

邻接矩阵实现：

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 300;
const int MAX_INT = ((1 << 31) - 1);
 
int n;                                      // 图中点的数目
int pre[MAXN];                              // 从 s - t 中的一个可行流中, 节点 i 的前序节点为 Pre[i];
bool vis[MAXN];                             // 标记一个点是否被访问过
int mp[MAXN][MAXN];                         // 记录图信息
 
bool bfs(int s, int t){
    queue <int> que;
    memset(vis, 0, sizeof(vis));
    memset(pre, -1, sizeof(pre));
    pre[s] = s;
    vis[s] = true;
    que.push(s);
    while(!que.empty()){
        int u = que.front();
        que.pop();
        for(int i = 1; i <= n; i++){
            if(mp[u][i] && !vis[i]){
                pre[i] = u;
                vis[i] = true;
                if(i == t) return true;
                que.push(i);
            }
        }
    }
    return false;
}
 
int EK(int s, int t){
    int ans = 0;
    while(bfs(s, t)){
        int mi = MAX_INT;
        for(int i = t; i != s; i = pre[i]){
            mi = min(mi, mp[pre[i]][i]);
        }
        for(int i = t; i != s; i = pre[i]){
            mp[pre[i]][i] -= mi;
            mp[i][pre[i]] += mi;
        }
        ans += mi;
    }
    return ans;
}

邻接表实现：

const int MAXN = 430;
const int MAX_INT = (1 << 30);
 
struct Edge{
    int v, nxt, w;
};
 
struct Node{
    int v, id;
};
 
int n, m, ecnt;
bool vis[MAXN];
int head[MAXN];
Node pre[MAXN];
Edge edge[MAXN];
 
void init(){
    ecnt = 0;
    memset(edge, 0, sizeof(edge));
    memset(head, -1, sizeof(head));
}
 
void addEdge(int u, int v, int w){
    edge[ecnt].v = v;
    edge[ecnt].w = w;
    edge[ecnt].nxt = head[u];
    head[u] = ecnt++;
}
 
bool bfs(int s, int t){
    queue <int> que;
    memset(vis, 0, sizeof(vis));
    memset(pre, -1, sizeof(pre));
    pre[s].v = s;
    vis[s] = true;
    que.push(s);
    while(!que.empty()){
        int u = que.front();
        que.pop();
        for(int i = head[u]; i + 1; i = edge[i].nxt){
            int v = edge[i].v;
            if(!vis[v] && edge[i].w){
                pre[v].v = u;
                pre[v].id = i;
                vis[v] = true;
                if(v == t) return true;
                que.push(v);
            }
        }
    }
    return false;
}
 
int EK(int s, int t){
    int ans = 0;
    while(bfs(s, t)){
        int mi = MAX_INT;
        for(int i = t; i != s; i = pre[i].v){
            mi = min(mi, edge[pre[i].id].w);
        }
        for(int i = t; i != s; i = pre[i].v){
            edge[pre[i].id].w -= mi;
            edge[pre[i].id ^ 1].w += mi;
        }
        ans += mi;
    }
    return ans;
}
 
// 加边
addEdge(u, v, w);
addEdge(v, u, 0);
// 调用
int ans = EK(s, t);

算法复杂度

每进行一次增广需要的时间复杂度为 bfs 的复杂度 + 更新残余网络的复杂度, 大约为 O(m)(m为图中的边的数目), 需要进行多少次增广呢, 假设每次增广只增加1, 则需要增广 nW 次(n为图中顶点的数目, W为图中边上的最大容量), .

敲黑板

Dinic 算法

算法思想

DINIC 在找增广路的时候也是找的最短增广路, 与 EK 算法不同的是 DINIC 算法并不是每次 bfs 只找一个增广路, 他会首先通过一次 bfs 为所有点添加一个标号, 构成一个层次图， 然后在层次图中寻找增广路进行更新。

算法流程

  1. 利用 BFS 对原来的图进行分层，即对每个结点进行标号， 这个标号的含义是当前结点距离源点的最短距离(假设每条边的距离都为1)，注意：构建层次图的时候所走的边的残余流量必须大于0

  2. 用 DFS 寻找一条从源点到汇点的增广路, 注意: 此处寻找增广路的时候要按照层次图的顺序, 即如果将边(u, v)纳入这条增广路的话必须满足, 其中 为结点 的编号。找到一条路后要根据这条增广路径上的所有边的残余流量的最小值更新所有边的残余流量(即正向弧 – l, 反向弧 + l).

  3. 重复步骤 2, 当找不到一条增广路的时候, 重复步骤 1, 重新建立层次图, 直到从源点不能到达汇点为止。

其实实现还是非常简单的，下面放一篇本人AC的代码，然后我再来讲一讲里面要注意的一些细节。（注意上面是BFS找1条，只有1条！！！）

#include<bits/stdc++.h>
using namespace std;
const int M=100005;
const int inf=99999999;
struct sd
{
    int to;
    int cap;
};
sd edge[M*2];
vector <int> next[M];
int cnt;
int layer[M];
void addedge(const int &from,const int &to,const int &flow)
{
    edge[cnt]=(sd){to,flow};
    next[from].push_back(cnt++);
    edge[cnt]=(sd){from,0};
    next[to].push_back(cnt++); 
}
bool BFS(int start,int end)
{
    queue <int> q;
    memset(layer,0,sizeof(layer));
    q.push(start);
    layer[start]=1;
    int now,nextt,tar;
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        for(register int i=next[now].size()-1;i>=0;i--)
        {
            tar=next[now][i];
            nextt=edge[tar].to;
            if(!edge[tar].cap||layer[nextt])continue;
            layer[nextt]=layer[now]+1;
            q.push(nextt);
        }
    }
    return layer[end];
}
int DFS(int now,int end,int value)
{
    if(now==end || value == 0)return value;
    int ret=0;
    int nextt,tar,flow;
    for(register int i=next[now].size()-1;i>=0;i--)
    {
        tar=next[now][i];
        nextt=edge[tar].to ;
        flow=edge[tar].cap ;
        if(!flow||layer[now]!=layer[nextt]-1)continue;
        int tmp=DFS(nextt,end,min(value-ret,flow));
        if(!tmp)continue;
        edge[tar].cap -=tmp;
        edge[tar^1].cap +=tmp;
        ret+=tmp;
        if(tmp == value) return ret;
    }
    return ret;
}
int Dinic(int start,int end)
{
    int ans=0;
    while(BFS(start,end))
    {
        ans+=DFS(start,end,inf);
    }
    return ans;
}
int main()
{
    int dot,line,st,en,a,c,b;
    scanf("%d%d%d%d",&dot,&line,&st,&en);
    for(register int i=1;i<=line;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        addedge(a,b,c);
    }
    printf("%d",Dinic(st,en));
    return 0;
}

注意：

  1. 我们最容易写错的东西其实就是dfs()，首先要注意就是每次dfs下去找最小的边的时候，一定要保证最小边不是0，如果是0，但是不判断的话，他就会一直把一个没有用的标记进行上传，非常的浪费时间。

  2. 最后如果增广失败不要忘记返回0（return 0），否则程序会出现奇怪的错误。

  3. 记住用链式前向星的与图论的链式前向星的一些不同的地方！还有反向弧减边的技巧。

下面给出一道板题和AC代码：大家仅供参考：

题目链接：
P2740 [USACO4.2]草地排水Drainage Ditches

AC code：

#include<bits/stdc++.h>
using namespace std;
const int inf =0x7fffffff;
struct sd{
	int v,next,to;
}edge[2005];
int n,m,cnt,head[2005],dep[2005],cur[2005],ans=0;
bool vis[2005];
void add(int a,int b,int c)
{
	edge[cnt].next=head[a];
	edge[cnt].to=b;
	edge[cnt].v=c;
	head[a]=cnt++;
}
int BFS()
{
	queue<int> q;
	memset(dep,0,sizeof(dep));
	dep[1]=1; q.push(1);
	while(!q.empty())
	{
		int now=q.front();q.pop(); 
		for(int i=head[now];i+1;i=edge[i].next)
		{
			if(!dep[edge[i].to]&&edge[i].v)
			{
				dep[edge[i].to]=dep[now]+1;
				q.push(edge[i].to);
			}
		}
	}
	return dep[n];
}
int dfs(int u,int w)
{
	if(u==n) return w;
	else
	{
		for(int &i=cur[u];i+1;i=edge[i].next)
		{
			if(edge[i].v&&dep[edge[i].to]==dep[u]+1)
			{
				int d=dfs(edge[i].to,min(w,edge[i].v));
				if(d)
				{
					edge[i].v-=d;
					edge[i^1].v+=d;
					return d; 
				} 
			}
		}
		return 0;//?
	}
}
int Dinic()
{
	while(BFS())
	{
		for(int i=1;i<=n;++i) cur[i]=head[i];
		while(int d=dfs(1,inf)) ans+=d;
	}
	return ans;
}
int main()
{
	memset(head,-1,sizeof(head));
	int a,b,c;
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,0);
	}
	printf("%d",Dinic());
	return 0;
}

【网络流】Dinic算法理解

原文地址：https://www.cnblogs.com/mudrobot/p/13329111.html

hmoban主题是根据ripro二开的主题，极致后台体验，无插件，集成会员系统
自学咖网 » Dinic算法理解

wen 普通

分享到：

相关推荐

Python从0到1丨细说图像增强及运算

摘要：本文主要讲解常见的图像锐化和边缘检测方法，即Roberts算子和Prewitt算子。 本文分享自华为云社区《[Python从零到壹] 五十七.图像增强及运算篇之图像锐化Roberts、Prewitt算子实现边缘检测...

Java 9 的模块（Module）系统

Java 的模块在Java 9中正式实装，一直没时间来研究一下这个东西，今天就和大家一起学习一下这个功能。 Java模块解决了什么问题 最近很多同学问我，胖哥，该怎么学习？该学习什么？这里胖哥也穿插说一下。不管学东西，一...

什么会使索引失效

1. 最左匹配原则 2.  全值匹配 3. 不在索引列上进行操作 4. is null, is not null 也无法使用索引 5. 在使用 不等于（!=）时无法使用索引 导致全表扫描 6. &nb...

Java 15 新特性：文本块

大家好，我是DD，今天继续来学点Java的新特性！ 假设有这样一个场景，我们需要做一个工具。用来自动生成项目文档，文档可以通过浏览器查看，所以最后产出物肯定是一堆html文件。为了让这些html文件更容易读，良好的格式肯...