Dinic算法

来自NOCOW

(跳转自Dinic)

跳转到：导航, 搜索

[编辑] 算法介绍

[编辑] 层次图

层次图，就是把原图中的点按照到到源的距离分“层”，只保留不同层之间的边的图。

[编辑] 算法流程

根据残量网络计算层次图。
在层次图中使用DFS进行增广直到不存在增广路
重复以上步骤直到无法增广

[编辑] 时间复杂度

设n为点数，m为边数，dfs遍历一次的时间复杂度为O(n*m)，最多dfs遍历n次，所以总的复杂度为O(n^2*m)。

[编辑] 代码实现

[编辑] 递归实现

代码简短，效率略低。

bool build()//建立层次图
{
	int x,y;
	memset(d,-1,sizeof(d));
	memset(G,-1,sizeof(G));
	bg=ed=d[s]=0;Q[ed++]=s;G[s]=g[s];
	while(bg<ed)
	{
		x=Q[bg++];
		for(int i=g[x];i+1;i=np[i])
		{
			y=to[i];
			if(cap[i]&&d[y]==-1)
			{
				d[y]=d[x]+1;G[y]=g[y];
				if(y==t)return true;
				Q[ed++]=y;
			}
		}
	}
	return false;
}
 
int find(int x,int low=inf)//进行增广
{
	if(x==t)return low;
	int ret=0,y;
	for(int &i=G[x];i+1;i=np[i])//注意i是引用
	{
		y=to[i];
		if(cap[i] && d[y]==d[x]+1 && (ret=find(y,low<?cap[i])))
		{
			cap[i]-=ret;cap[vp[i]]+=ret;
			return ret;
		}
	}
	return 0;
}
 
int dinic()//主过程
{
	int flow;
	while(build())
		while(flow=find(s))
			cnt+=flow;
	return 0;
}

[编辑] 非递归实现

效率更高，但代码量略有些大。

//Author: dd_engi
void Dinic()
{
    for(;;){
        BFS();
        if(D[T]==-1)break;
        int path_n=0;
        int x=S;
        memcpy(cur,E,sizeof(cur));
        for(;;){
            if(x==T){
                int mink=-1,delta=INT_MAX;
                for(int i=0;i<path_n;++i){
                    if(path[i]->c<delta){
                        delta=path[i]->c;
                        mink=i;
                    }
                }
                for(int i=0;i<path_n;++i){
                    path[i]->c-=delta;
                    path[i]->back->c+=delta;
                }
                path_n=mink;
                x=path[path_n]->x;
            }
            edge* e;
            for(e=cur[x];e;e=e->next){
                if(e->c==0)
                    continue;
                int y=e->y;
                if(D[x]+1==D[y])
                    break;
            }
            cur[x]=e;
            if(e){
                path[path_n++]=e;
                x=e->y;
            }
            else{
                if(path_n==0)
                    break;
                D[x]=-1;
                --path_n;
                x=path[path_n]->x;
            }
        }
    }
}