有向强连通和网络流大讲堂——史无前例求解最大流（最小割）、最小费用最大流

有向强连通和网络流大讲堂——史无前例最大流（最小割）、最小费用最大流

本文内容框架（未完成）：

§1网络流的基本概念

§2最大流问题

§2.1Ford-Fulkerson方法（增大路径最大流算法）

§2.2Edmonds-Karp（EK）算法实现

§2.3Dinic算法

§2.4SAP算法(最短路径增广算法)

§2.5Preflow push method(预流-推进最大流方法）

§3最小费用最大流问题

§4有向图强连通分量的问题

Kosaraju算法、Tranjan算法、Gabow算法

§5问题归约

§6小结

 

 

§1网络流的基本概念

╔ 

一、流网络:网络或容量网络指的是一个连通的赋权有向图 D＝ （V、E、C） ， 其中V 是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点（源点）s和一个终点t（汇点）。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。

       二、流：设G(E,V)是一个流网络，那么G的流是定义在V*V上的一个实值函数f,并且满足一下三个性质:

            1)容量限制：f(u,v)<=c(u,v)

            2)反对称性：f(u,v)=-f(v,u)

            3)流守恒性：简单点说就是：对于非源点，它流出的流量总和为0，对于非汇点，流入它的流量总和为0

╝①

§2最大流问题

╔

       那么给定一个流网络，最大流问题就是求该流网络中，原点流出的最大流量或者是流入汇点的最大流量。如何求解这个问题：要引入一下三个概念。

        一、残余网络：在一个流网络中，给定一个流，那么我们可以根据这个流计算出对应的残余网络cf(u,v)=c(u,v)-f(u,v),值得注意的一点就是，如果f(u,v)为负，那么cf(u,v)就大于c(u,v)

        二、增广路径：这个其实很简单，在一个残余网络中，任何一条从源点S到汇点T的路径（cf(u,v)>0）都是增广路径。一条增广路径的流量是路径中cf(u,v)中的最小值。

        三、网络流的割：流网络G(E,V)的割（S,T）将流网络分解为S，T(V-S)两个部分，其中源点s属于S，汇点t属于T。于是我们定义割(S,T)的净流f(S,T)和容量c(S,T).其中f(S,T)为从S到T的流量总和减去从T到S的流量总和。而c(S,T)为从S到T的容量总和。

        基于以上三个概念，有如下总要定理：

最大流最小割定理

       对于一个流网络G=(E,V)，一下三个命题两两等价

       1）f是G的一个最大流

       2）残余网络Gf不存在增广路径

       3）对于G的某个割（S,T），f=c(S,T)且c(S,T)是G的某个最小割

╝①

§2.1Ford-Fulkerson方法（增大路径最大流方法）

Ford-Fulkerson方法依赖于三种重要思想，这三个思想就是在网络流基础中提到的：残留网络，增广路径和割。Ford-Fulkerson方法是一种迭代的方法。开始时，对所有的u，v∈V有f(u,v)=0，即初始状态时流的值为0。在每次迭代中，可通过寻找一条“增广路径”来增加流值。增广路径可以看成是从源点s到汇点t之间的一条路径，沿该路径可以压入更多的流，从而增加流的值。反复进行这一过程，直至增广路径都被找出来，根据最大流最小割定理，当不包含增广路径时，f是G中的一个最大流。在算法导论中给出的Ford-Fulkerson实现代码如下：

     FORD_FULKERSON(G,s,t)

     1   for each edge(u,v)∈E[G]

     2        do f[u,v] <— 0

     3            f[v,u] <— 0

     4   while there exists a path p from s to t in the residual network Gf

     5        do cf(p) <— min{ cf(u,v) : (u,v) is in p }

     6        for each edge(u,v) in p

     7             do f[u,v] <— f[u,v]+cf(p)         //对于在增广路径上的正向的边，加上增加的流

     8                  f[v,u] <— -f[u,v]                //对于反向的边，根据反对称性求

     第1~3行初始化各条边的流为0，第4~8就是不断在残留网络Gf中寻找增广路径，并沿着增广路径的方向更新流的值，直到找不到增广路径为止。而最后的最大流也就是每次增加的流值cf(p)之和。在实际的实现过程中，我们可以对上述代码做些调整来达到更好的效果。如果我们采用上面的方法，我们就要保存两个数组，一个是每条边的容量数组c，一个就是上面的每条边的流值数组f，在增广路径中判断顶点u到v是否相同时我们必须判断c[u][v]-f[u][v]是否大于0，但是因为在寻找增广路径时是对残留网络进行查找，所以我们可以只保存一个数组c来表示残留网络的每条边的容量就可以了，这样我们在2~3行的初始化时，初始化每条边的残留网络的容量为G的每条边的容量（因为每条边的初始流值为0）。而更新时，改变7~8行的操作，对于在残留网络上的边(u,v)执行c[u][v]-=cf(p)，而对其反向的边(v,u)执行c[v][u]+=cf(p)即可。

《算法导论》中严格定义Ford-FullKerson方法是一种方法而不是一种算法，也许是因为其没有给出具体寻找增广路径的方法。

 

Ford-Fulkerson算法实现

Ford-Fulkerson算法使用DFS查找增广路径，下面附上两个版本的实现，大同小异

╔

#include<stdio.h>
#include<string.h>
#define maxn 16
#define inf 999999
int s,t,i,n,m,u,v,w,flow,maxflow;
int vis[maxn];
int c[maxn][maxn];
int dfs(int u,int low)
{
    int i,flow;
    if(u==t)
        return low;
    if(vis[u])
        return 0;
    vis[u]=1;
    for(i=1;i<=n;i++)
        if(c[u][i]&&(flow=dfs(i,low<c[u][i]?low:c[u][i])))
        {
            c[u][i]-=flow;
            c[i][u]+=flow;
            return flow;
        }
    return 0;
}
int main()
{
    int ca,k=1;
    scanf("%d",&ca);
    while(ca--)
    {
        scanf("%d%d",&n,&m);
        memset(c,0,sizeof(c));
        memset(vis,0,sizeof(vis));
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            c[u][v]+=w;
        }
        s=1;t=n;
        maxflow=0;
        while(flow=dfs(s,inf))
        {
            maxflow+=flow;
            memset(vis,0,sizeof(vis));
        }
        printf("Case %d: %d\n",k++,maxflow);
    }
    return 0;
}

 

#include<stdio.h>
#include<string.h>
#define maxn 16
#define inf 9999999
int c[maxn][maxn];
int s,t,i,k,u,v,w,n,m;
int flow,maxflow;
int vis[maxn];
int dfs(int u,int low)
{
    int i,flow;
    int sum=0;
    if(u==t)
        return low;
    if(vis[u])
        return 0;
    vis[u]=1;
    for(i=1;i<=n;i++)
        if(c[u][i]&&(flow=dfs(i,low<c[u][i]?low:c[u][i])))
        {
            sum+=flow;
            low-=flow;
            c[u][i]-=flow;
            c[i][u]+=flow;
            if(!low)
                break;
        }
    return sum;
}
int main()
{
    int ca,k=1;
    scanf("%d",&ca);
    while(ca--)
    {
        memset(vis,0,sizeof(vis));
        memset(c,0,sizeof(c));
        scanf("%d%d",&n,&m);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            c[u][v]+=w;
        }
        s=1;t=n;
        maxflow=0;
        while(flow=dfs(s,inf))
        {
            maxflow+=flow;
            memset(vis,0,sizeof(vis));
        }
        printf("Case %d: %d\n",k++,maxflow);
    }
    return 0;
}

 ╝②

 

§2.2Edmonds-Karp（EK）算法实现

Edmonds-Karp是一种求网络最大流的算法，最为Ford-Fulkson类算法中最简单的一个算法，与Ford-Fulkerson算法不同的是Edmonds-Karp要求每次找长度最短的增广路径,即使用BFS查找增广路径。

时间复杂度是O(n·m²)，空间复杂度是O(n²)。

void ford_fulkerson(int s,int e)
{
	queue<int>Q;
	int u,v;
	while(1)                          
	{
		Maxflow=0;//最大流初始化
		memset(maxflow,0,sizeof(maxflow));//每次寻找增广路径都将每个点的流入容量置为0
		memset(visit,0,sizeof(visit));//标记一个点是否已经压入队列
		maxflow[s]=INT_MAX;//源点的容量置为正无穷
		Q.push(s);   // 将源点压入队列
		while(!Q.empty())   //当队列不为空
		{
			u=Q.front();
			Q.pop();
			for(v=1;v<=N;v++)   
			{
				if(!visit[v]&&flow[u][v]>0) 
				{
					visit[v]=1;
					father[v]=u;//记录下他的父亲方便往后的正反向更新
					Q.push(v);
					maxflow[v]=(maxflow[u]<flow[u][v]?maxflow[u]:flow[u][v]);//当前点的容量为父亲点容量与边流量的较小者
				}
			}
			if(maxflow[e]>0) //如果找到了汇点并且汇点容量不为0则清空队列。
			{
				while(!Q.empty())
					Q.pop();
				break;
			}
		}
		if(maxflow[e]==0)//已经找不到到汇点的增光路经了，就退出整个循环
			break;
		for(i=e;i!=s;i=father[i])
		{
			flow[father[i]][i]-=maxflow[e];//正向更新
			flow[i][father[i]]+=maxflow[e];//反向更新
		}
		Maxflow+=maxflow[e];//更新最大流
	}
}

§2.3Dinic算法

 

 

Dinic 算法是其中一种比较高效的方法，是EK算法的改进，减少查找增广路径次数，其复杂度为 O(V²*E)。

 

Dinic 算法的步骤

1) 计算残余网络的层次图。我们定义 h 为顶点 i 距离源 S 所经过到最小边数，求出所有顶点的 h 值，h[] 值相同的顶点属于同一层，这就是网络的层次图。

2) 在层次图上进行 BFS 增广，直到不存在增广路径。这时求得的增广路径上顶点是分层的，路径上不可能存在两个顶点属于同一层，即 h== h[j] (i!= j )。同时，求得层次图后，我们可以在层次图上进行多次增广。

3) 重复 1 和 2。直到不存在增广路径。

可知，Dinic 算法找到的增广路径是最短的，即经过的顶点数最少。再者，Dinic 算法找一条增广路径同时可以找到多条，类似增广路径树。比如我们找到了一条增广路径，这条增广路径所增加的流量为 C,则这条增广路径上必然有一条边<i,j>残余容量为 C，这是我们不必又从起点开始寻找增广路，而是从 i 顶点出发找增广路，这样就减少了重复计算，提高了效率。

 

Dinic算法实现

╔

 

//--------Dinic的非递归正向实现---------
#define NOT(x) (x&1?x+1:x-1)

struct Edge
{
    int u;
    int value;
    int next;
}edge[MAXM*2];
int level[MAXN],queue[MAXN],node[MAXN],variednode[MAXN];//level给每一个节点分级，即分层；queue分层时当队列用，找增广路时
int front,rear;//当栈用；node[i]为结点i的指针；variednode可变的结点指针（原本是node的复制，但是他不断变化）；front，rear
int index;//即队列的首尾；top即栈顶；index即作为edge的下标；
int top;

void Build_Graph(int m)//建图即建立网络
{
    int v,u,value;
    index=0; memset(node,-1,sizeof(node));
    for(int i=0;i<m;i++)
    {
        scanf("%d %d %d",&v,&u,&value);
        ++index;                 //这里用数组模拟指针，模拟链表结构
        edge[index].u=u;           //重在自己慢慢体会，讲不出来效果的……
        edge[index].value=value;
        edge[index].next=node[v];
        node[v]=index;/////建立原网络

        ++index;
        edge[index].u=v;
        edge[index].value=0;
        edge[index].next=node[u];
        node[u]=index;/////建立反网络
    }
}

int Dinic(int source,int sink,int n)
{
    int maxflow=0;
    int v,u,value;
    while(true)
    {
        memset(level,0,sizeof(level));
        front=rear=0; level[source]=1;
        queue[0]=source;
        while(front<=rear)/////传说中的分层
        {
            v=queue[front++];//注意这里的queue当队列用储存的是结点
            for(int i=node[v];i!=-1;i=edge[i].next)
            {
                u=edge[i].u; value=edge[i].value;
                if(value && level[u]==0)
                {
                    level[u]=level[v]+1;
                    queue[++rear]=u;
                    if(u==sink) break;
                }
            }
            if(u==sink) break;
        }

        if(level[sink]==0)    break;//这个就是判断是否存在增广路，没有就结束了

        for(int i=1;i<=n;i++)    variednode[i]=node[i];//看variednode——node的复制，以后就不断变化。这就是优化，记录下次开始访问的边。
        edge[0].u=source;    top=0;    queue[++top]=0;//这里的所做是为了“凑”下边的循环，这里的queue做栈用储存边的下标
        while(top)//////求该分层下的最短增广路
        {
            int i;  v=edge[queue[top]].u;
            for(i=variednode[v];i!=-1;i=edge[i].next)
            {
                u=edge[i].u; value=edge[i].value;
                if(value && level[u]==level[v]+1)
                {
                    queue[++top]=i;
                    variednode[v]=edge[i].next;
                    break;
                }
            }
            if(i==-1)    { variednode[v]=-1;top--;continue; }//若该点四周不存在最短增广路，则直接variednode[v]=-1；以防下次做
                                                       //多余的查找。top--退一条边，再找

            if(u==sink)//找到一条边就判断一下该点是不是sink，不是继续向下找
            {
                int min=0x7fffffff,flag;
                for(i=2;i<=top;i++)
                    if(min>edge[i].value)
                        min=edge[i].value;//找到最大流量
                for(i=top;i>1;i--)
                {
                    if(min==edge[queue[i]].value)
                        flag=i;//更新该正向路径的各个流量，并标记出第一个流量变为0的边所在的栈位

                    edge[queue[i]].value-=min;
                    edge[NOT(queue[i])].value+=min;//看看怎么建图的吧    }
                top=flag-1;//更新top
                maxflow+=min;//更新maxflow
            }
        }
    }

    return maxflow;
}

 ╝④

 

§2.4SAP算法(最短路径增广算法)

SAP算法计算的反向层次图即从当前顶点到汇点t的距离，而Dinic算法是从源点s到当前顶点的距离。

 

 

SAP算法流程

1、定义距离标号为各点到汇点距离的下界(即最短距离)。

2、在初始距离标号的基础上，不断沿着可行弧找增广路。可行弧的定义为{( i , j ) , h[ i ]==h[ j ]+1 };

3、遍历当前节点完以后，为了保证下次再来的时候有路可走，重新标号当前距离。

    h[ i ] = min（h[ j ] +1）；

4、检查重新标记的顶点，若其为原点，且被标记的高度等于节点个数时，图中已经不存在增广路，算法可结束。否则继续从原点开始遍历

 

SAP算法实现

 

#include <iostream>  
    #include <cstring>  
    #include <cstdlib>  
      
    usingnamespace std;  
      
    constint Max =225;  
    constint oo =210000000;  
      
    int n,m,c[Max][Max],r[Max][Max],c1[Max][Max],source,sink；  
      
    //c1是c的反向网络，用于dis数组的初始化  
int dis[Max];  
      
    void initialize()// 初始化dis数组  
    {  
         int q[Max],head =0, tail =0;//BFS队列  
         memset(dis,0,sizeof(dis));  
         q[++head] = sink;  
         while(tail < head)  
         {  
             int u = q[++tail], v;  
             for(v =0; v <= sink; v++)  
             {  
                   if(!dis[v] && c1[u][v] >0)  
                   {  
                       dis[v] = dis[u] +1;  
                       q[++head] = v;  
                   }  
             }  
         }  
    }  
      
    int maxflow_sap()  
    {  
        initialize();  
        int top = source, pre[Max], flow =0, i, j, k, low[Max];  
      
        // top是当前增广路中最前面一个点。  
        memset(low,0,sizeof(low));//low数组用于保存路径中的最小容量  
while(dis[source] < n)  
        {  
            bool flag =false;  
            low[source] = oo;  
            for(i =0; i <= sink; i++)//找允许弧，根据允许弧的定义  
            {  
                if(r[top][i] >0&& dis[top] == dis[i] +1)  
                {  
                    flag =true;  
                    break;  
                }  
            }  
            if(flag)// 如果找到允许弧  
            {  
                low[i] = r[top][i];  
                if(low[i] > low[top]) low[i] = low[top];//更新low  
                pre[i] = top; top = i;  
                if(top == sink)// 如果找到一条增广路了  
                {  
                    flow += low[sink];  
                    j = top;  
                    while(j != source)// 路径回溯更新残留网络  
                    {  
                        k = pre[j];  
                        r[k][j] -= low[sink];  
                        r[j][k] += low[sink];  
                        j = k;  
                    }  
                    top = source;//从头开始再找最短路  
                    memset(low,0,sizeof(low));  
                }  
            }  
            else// 如果没有允许弧  
            {  
                int mindis =10000000;  
                for(j =0; j <= sink; j++)//找和top相邻dis最小的点  
                {  
                    if(r[top][j] >0&& mindis > dis[j] +1)  
                        mindis = dis[j] +1;  
                }  
                dis[top] = mindis;//更新top的距离值  
if(top != source) top = pre[top];// 回溯找另外的路  
            }  
        }  
        return(flow);  
    }

 

 

SAP算法使用GAP优化实现

 

/*
    sap+gap优化,采用邻接矩正
    时间复杂度:O(mn^2)
*/

#include<iostream>
#include<queue>
using namespace std;

const int msize=205;     //最大顶点数
const int inf=0x7fffffff;

int dis[msize];   //标号
int r[msize][msize];   //残留网络,初始为原图
int num[msize];    //num[i]表示标号为i的顶点数有多少
int pre[msize];
int n,m,src,des;    //n个顶点,m条边,源点src,汇点des

void rev_bfs()   //反向bfs计算标号,汇点des标号为0
{
    int i,k;
    for(i=1;i<=n;i++)
    {
        dis[i]=n;
        num[i]=0;
    }

    queue<int> q;
    q.push(des);
    dis[des]=0;
    num[0]=1;
    while(!q.empty())
    {
        k=q.front();
        q.pop();
        for(i=1;i<=n;i++)
        {
            if(dis[i]==n&&r[i][k]>0)
            {
                dis[i]=dis[k]+1;
                q.push(i);
                num[dis[i]]++;
            }
        }
    }
}

int findArc(int i)
{
    for(int j=1;j<=n;j++)
    {
        if(r[i][j]>0&&dis[i]==dis[j]+1)
            return j;
    }
    return -1;
}

int reLable(int i)
{
    int mindis=n;
    for(int j=1;j<=n;j++)
    {
        if(r[i][j]>0) 
            mindis=mindis<dis[j]? mindis:dis[j];
    }
    return mindis;
}

int maxFlow()
{
    rev_bfs();

    int totalflow=0, i=src, j, k;
    int d;     //增量

    pre[src]=-1;
    while(dis[src]<n)
    {
        j=findArc(i);
        if(j>=0)
        {
            pre[j]=i;
            i=j;
            if(i==des)
            {
                d=inf;
                for(k=des;k!=src;k=pre[k])
                    d=d<r[pre[k]][k]? d:r[pre[k]][k];
                for(k=des;k!=src;k=pre[k])
                {
                    r[pre[k]][k]-=d;
                    r[k][pre[k]]+=d;
                }
                totalflow+=d;
                i=src;
            }
        }
        else
        {
            --num[dis[i]];
            if(0==num[dis[i]]) return totalflow;
            int x=reLable(i);
            dis[i]=x+1;
            num[dis[i]]++;
            if(i!=src) i=pre[i];
        }
    }
    return totalflow;
}

int main()
{
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        int i;
        int u,v,w;
        memset(r,0,sizeof(r));
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            r[u][v]+=w;
        }
        src=1;
        des=n;
        printf("%d\n",maxFlow());
    }
    return 0;
}

 

 

 

 

 

 

 

 

§2.5Preflow push method(预流-推进最大流方法）

 

在一个流网络中，预流（preflow)是一个正边流的集合，满足一下条件：每条边的流不大于该边的容量，且对于每个内部结点，其上的流入量不小于它的流出量。活动顶点是一个流入量大于流出量的内部结点。把活动顶点v的流入量和流出量的差称为该顶点的盈余量（excess）e(v)。

最大推进：如果一个顶点v对每一个邻点u都以容量大小（c<v,u>）的流向前推进过，就说顶点v达到最大推进。

 

Preflow push method的原理

Preflow push method是给源点一个足够大（等于源点邻接边的容量之和）的流，向邻近结点推进（push)，得到了一个活动顶点（还没有流出，只是流入）集合，然后将这个集合的点沿着路径推进（流出）不断的减小盈余量（或者是回退给上一个顶点），直到没有活动顶点为止。每次推进的流量是边的容量。

增大路径算法总是维持一个可行流（流出量等于流入量）：它沿着增大路径增加流，最终得到最大流。而预流-推进算法维持的最大流不是可行流，因为某些顶点的流入量比流出量要大：它们通过这些顶点推进(push)流，直到达到一个可行流。再用水流来说明两者的区别：增大路径算法相当于查找一个所有河流，获得每条河流的最大流量（其中流量最小作为一条河流的最大流量，否则会出现决堤），最后把每条河流的最大流量累加就是最大流；预流-推进方法相当于水库放水的过程，即最大流相当于从水库以河道的最大容量向下游推进的过程。

 

Preflow push 方法的流程

1.给源点s一个足够（等于源点邻接边的容量之和）的流，流向它的邻近顶点，使它的邻近顶点构成一个活动顶点的集合A

2.遍历活动顶点集合A的每一个点v，对v进行如下操作：

（1）对v的每一条邻接边以边容量的流向前推进流（如果每条邻边都以边容量推进过的（达到最大推进），则执行（2）），并将该顶点加入集合A

（2）若（1）操作后顶点v的还有盈余量(e(v)>0)，则将流量退回（逆推进）给上一个顶点（流给它的顶点），最后将v从集合A中移除，其中退回给的上一个顶点就变成了活动顶点要进入集合A

3.直到活动顶点集合A为空为止，流向汇点t的流量就是最大流量。

 

退回操作释疑

这里主要的难点就是为什么要做退回（逆推进）的操作。用一个例子来说明即可：对于顶点v，它有A和B两条路径到达汇点t，v的流入量是5，向A路径的第一个顶点a推进的流量是4（c<v,a>=4），那么只能向B路径的一个顶点b推进的流量是1（这时c<v,b>=3），但是在A路径最终只有2流向汇点t，出现了盈余量，在B路径去没有达到最大流量，那么应该把A路径的盈余量转移到B路径去推进，这得靠退回（逆推进）操作来完成。退回操作就是把盈余量逆推进给上一个顶点

 

Push relabel 算法（压入与重标记方法）

 

Preflow push方法是将活动顶点沿着邻接边以边的容量（c<v,u>）为最大流量向前推进流，以源点s进行BFS分层得到的树结构，同一层（到源点s路径长度相等）的顶点的地位是一样的，同一层的每个顶点都可以得到最大盈余量（c<v,u>），如果盈余量大于0，则要做退回操作。Push relabel算法的原理是以高度来表示由源点s向前的层次，源点s层次最高，每次推进操作是从高顶点往低顶点压入，如果顶点v还有盈余量（邻近顶点u高度大于等于v的高度，或者有剩余）则增加高度（就是Preflow push的退回操作）。

 

Push Relabel算法的流程

1）、构造初始流。将源点高度标记为n，其余点高度均为0；

2）、如果残留网络中不存在活结点，则算法结束。否则继续执行下一步；

3）、选取活结点，如果该结点出边为可推流边，则沿此边推流，否则将该节点高度加1，执行步骤2）。

 

压入与重标记算法实现

╔

 

struct Node{
    int v;
    Node *next;
}
Node g[MAX];    //用邻接表存储
int resi[MAX][MAX];   //残留容量
int e[MAX],h[MAX];   //顶点的余流和高度
int Push_Relabel(int s,int t,int n){
    queue<int> que;
    int i,u,_min,sum=0;
    Node *p;
    //初始化顶点高度和余流
    memset(e,0,sizeof(e));
    memset(h,0,sizeof(h));
    h[s]=n;
    e[0]=(1<<30);
    que.push(s);   //将源点进队
    while(!que.empty()){
        u=que.front();
        que.pop();
        for(p=g[u].next;p;p=p->next){
            _min=resi[u][p->v]<e[u]?resi[u][p->v]:e[u];  //取顶点余流和相邻边的残留容量的最小值
            //如果h[u]<=h[p->v]，则应执行中标记操作；如果h[u]==h[p->v]+1，则执行压入操作
            if(_min&&(h[u]==h[p->v]+1 || u==s)){
                resi[u][p->v]-=_min;
                resi[p->v][u]+=_min;
                e[u]-=_min;
                e[p->v]+=_min;
                if(p->v==t)sum+=_min;   //如果到达了汇点，就将流值加入到最大流中
                else if(p->v!=s)que.push(p->v);   //只有既不是源点也不是汇点才进队
            }
        }
        //如果不是源点且仍有余流，则重标记高度再进队。
        //这里只是简单的将高度增加了一个单位，也可以向上面所说的一样赋值为最低的相邻顶点的高度高一个单位
        if(u!=s&&e[u]){ 
            h[u]++;
            que.push(u);
        }
    }
    return sum;
}

 

 ╝③

 

疑问：

个人一直都有一个疑问就是Push relabel算法怎么没有进行退回操作，只是把高度增加（貌似只是为了推进），并没有把盈余量逆推进给指向它的顶点，还是没有解决上面退回释疑的情况？

 

Relabel to front 算法（重标记与前移算法）

 

 

Relabel-to-Front使用一个链表保存盈余顶点（盈余量>0），用Discharge操作不断使盈余顶点不再溢出。Discharge的操作过程是：若找不到可被压入的临边，则重标记，否则对临边压入，直至点不再盈余。算法的主过程是：首先将源点出发的所有边充满，然后将除源和汇外的所有顶点保存在一个链表里，从链表头开始进行Discharge，如果完成后顶点的高度有所增加，则将这个顶点置于链表的头部，对下一个顶点开始Discharge。

Relabel-to-Front算法的时间复杂度是O(V^3)，还有一个叫Highest Label Preflow Push的算法复杂度据说是O(V^2*E^0.5)。我研究了一下HLPP，感觉它和Relabel-to-Front本质上没有区别，因为Relabel-to-Front每次前移的都是高度最高的顶点，所以也相当于每次选择最高的标号进行更新。还有一个感觉也会很好实现的算法是使用队列维护盈余顶点，每次对pop出来的顶点discharge，出现了新的盈余顶点时入队。

 

 

最高标号预流推进算法（暂时搁浅）

 

§3最小费用最大流问题

 

最小费用最大流问题求解算法有

 

1、 连续最短路算法（Successive Shortest Path）；

2、 消圈算法（Cycle Canceling）；

3、 原始对偶算法（Primal Dual）；

4、 网络单纯形（Network Simplex）。

 

 

 

§4有向图强连通分量的问题

 

 

有向图的强连通分支算法(strongly connected component)，该算法是图深度优先搜索算法的另一重要应用。强分支算法可以将一个大图分解成多个连通分支，某些有向图算法可以分别在各个联通分支上独立运行，最后再根据分支之间的关系将所有的解组合起来。

在无向图中，如果顶点s到t有一条路径，则可以知道从t到s也有一条路径；在有向无环图中个，如果顶点s到t有一条有向路径，则可以知道从t到s必定没有一条有向路径；对于一般有向图，如果顶点s到t有一条有向路径，但是无法确定从t到s是否有一条有向路径。可以借助强连通分支来研究一般有向图中顶点之间的互达性。

有向图G=(V, E)的一个强连通分支就是一个最大的顶点子集C，对于C中每对顶点(s, t)，有s和t是强连通的，并且t和 s也是强连通的，即顶点s和t是互达的。图中给出了强连通分支的例子。我们将分别讨论3种有向图中寻找强连通分支的算法。

3种算法分别为Kosaraju算法、Tarjan算法和Gabow算法，它们都可以在线性时间内找到图的强连通分支。

 

 

╔ 

一、     Kosaraju算法

1.      算法思路

基本思路：

这个算法可以说是最容易理解，最通用的算法，其比较关键的部分是同时应用了原图G和反图GT。(步骤1)先用对原图G进行深搜形成森林(树)，（步骤2）然后任选一棵树对其进行深搜(注意这次深搜节点A能往子节点B走的要求是EAB存在于反图GT)，能遍历到的顶点就是一个强连通分量。余下部分和原来的森林一起组成一个新的森林，继续步骤2直到 没有顶点为止。

改进思路：

当然，基本思路实现起来是比较麻烦的(因为步骤2每次对一棵树进行深搜时，可能深搜到其他树上去，这是不允许的，强连通分量只能存在单棵树中(由开篇第一句话可知))，我们当然不这么做，我们可以巧妙的选择第二深搜选择的树的顺序，使其不可能深搜到其他树上去。想象一下，如果步骤2是从森林里选择树，那么哪个树是不连通(对于GT来说)到其他树上的呢？就是最后遍历出来的树，它的根节点在步骤1的遍历中离开时间最晚，而且可知它也是该树中离开时间最晚的那个节点。这给我们提供了很好的选择，在第一次深搜遍历时，记录时间i离开的顶点j，即numb[i]=j。那么，我们每次只需找到没有找过的顶点中具有最晚离开时间的顶点直接深搜(对于GT来说)就可以了。每次深搜都得到一个强连通分量。 

隐藏性质:

    分 析到这里，我们已经知道怎么求强连通分量了。但是，大家有没有注意到我们在第二次深搜选择树的顺序有一个特点呢？如果在看上述思路的时候，你的脑子在思 考，相信你已经知道了！！！它就是：如果我们把求出来的每个强连通分量收缩成一个点，并且用求出每个强连通分量的顺序来标记收缩后的节点，那么这个顺序其 实就是强连通分量收缩成点后形成的有向无环图的拓扑序列。为什么呢？首先，应该明确搜索后的图一定是有向无环图呢？废话，如果还有环，那么环上的顶点对应 的所有原来图上的顶点构成一个强连通分量，而不是构成环上那么多点对应的独自的强连通分量了。然后就是为什么是拓扑序列，我们在改进分析的时候，不是先选 的树不会连通到其他树上（对于反图GT来说），也就是后选的树没有连通到先选的树，也即先出现的强连通分量收缩的点只能指向后出现的强连通分量收缩的点。那么拓扑序列不是理所当然的吗？这就是Kosaraju算法的一个隐藏性质。 

2.      伪代码

Kosaraju_Algorithm:

 step1：对原图G进行深度优先遍历，记录每个节点的离开时间。

 step2：选择具有最晚离开时间的顶点，对反图GT进行遍历，删除能够遍历到的顶点，这些顶点构成一个强连通分量。

 step3：如果还有顶点没有删除，继续step2，否则算法结束。 

3.      实现代码：

#include <iostream>

using namespace std;

 

const int MAXN = 110;

 

typedef int AdjTable[MAXN]; //邻接表类型

 

int      n;

bool     flag[MAXN]; //访问标志数组

int      belg[MAXN]; //存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量

int      numb[MAXN]; //结束时间标记,其中numb[i]表示离开时间为i的顶点

AdjTable adj[MAXN], radj[MAXN]; //邻接表,逆邻接表

 

//用于第一次深搜,求得numb[1..n]的值

void VisitOne(int cur, int &sig)

{

  flag[cur] = true;

 

  for ( int i=1; i<=adj[cur][0]; ++i )

  {

     if ( false==flag[adj[cur][i]] )

     {

         VisitOne(adj[cur][i],sig);

     }

  }

 

  numb[++sig] = cur;

}

 

//用于第二次深搜,求得belg[1..n]的值

void VisitTwo(int cur, int sig)

{

  flag[cur] = true;

  belg[cur] = sig;

 

  for ( int i=1; i<=radj[cur][0]; ++i )

  {

     if ( false==flag[radj[cur][i]] )

     {

         VisitTwo(radj[cur][i],sig);

     }

  }

}

 

//Kosaraju算法,返回为强连通分量个数

int Kosaraju_StronglyConnectedComponent()

{

  int  i, sig;

 

  //第一次深搜

  memset(flag+1,0,sizeof(bool)*n);

  for ( sig=0,i=1; i<=n; ++i )

  {

     if ( false==flag[i] )

     {

         VisitOne(i,sig);

     }

  }

 

  //第二次深搜

  memset(flag+1,0,sizeof(bool)*n);

  for ( sig=0,i=n; i>0; --i )

  {

     if ( false==flag[numb[i]] )

     {

         VisitTwo(numb[i],++sig);

     }

  }

 

  return sig;  

}

 

二、     Trajan算法

1.      算法思路：

这 个算法思路不难理解，由开篇第一句话可知，任何一个强连通分量，必定是对原图的深度优先搜索树的子树。那么其实，我们只要确定每个强连通分量的子树的根， 然后根据这些根从树的最低层开始，一个一个的拿出强连通分量即可。那么身下的问题就只剩下如何确定强连通分量的根和如何从最低层开始拿出强连通分量了。

那么如何确定强连通分量的根，在这里我们维护两个数组，一个是indx[1..n]，一个是mlik[1..n]，其中indx[i]表示顶点i开始访问时间，mlik[i]为与顶点i邻接的顶点未删除顶点j的mlik[j]和mlik[i]的最小值(mlik[i]初始化为indx[i])。这样，在一次深搜的回溯过程中，如果发现mlik[i]==indx[i]那么，当前顶点就是一个强连通分量的根，为什么呢？因为如果它不是强连通分量的跟，那么它一定是属于另一个强连通分量，而且它的根是当前顶点的祖宗，那么存在包含当前顶点的到其祖宗的回路，可知mlik[i]一定被更改为一个比indx[i]更小的值。

至于如何拿出强连通分量，这个其实很简单，如果当前节点为一个强连通分量的根，那么它的强连通分量一定是以该根为根节点的(剩下节点)子 树。在深度优先遍历的时候维护一个堆栈，每次访问一个新节点，就压入堆栈。现在知道如何拿出了强连通分量了吧？是的，因为这个强连通分量时最先被压人堆栈 的，那么当前节点以后压入堆栈的并且仍在堆栈中的节点都属于这个强连通分量。当然有人会问真的吗？假设在当前节点压入堆栈以后压入并且还存在，同时它不属 于该强连通分量，那么它一定属于另一个强连通分量，但当前节点是它的根的祖宗，那么这个强连通分量应该在此之前已经被拿出。现在没有疑问了吧，那么算法介 绍就完了。 

2.      伪代码：

Tarjan_Algorithm:

   step1:

   找一个没有被访问过的节点v，goto step2(v)。否则，算法结束。

      step2(v):

       初始化indx[v]和mlik[v]

       对于v所有的邻接顶点u：

              1)     如果没有访问过，则step2(u),同时维护mlik[v]

              2)     如果访问过，但没有删除，维护mlik[v]

       如果indx[v]==mlik[v]，那么输出相应的强连通分量 

3.      实现代码

#include <iostream>

using namespace std;

 

const int  MAXN    = 110;

const char NOTVIS  = 0x00;   //顶点没有访问过的状态

const char VIS     = 0x01;   //顶点访问过,但没有删除的状态

const char OVER    = 0x02;   //顶点删除的状态

 

typedef int AdjTable[MAXN];  //邻接表类型

 

int      n;

char     flag[MAXN];         //用于标记顶点状态,状态有NOTVIS,VIS,OVER

int      belg[MAXN];         //存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量

int      stck[MAXN];         //堆栈,辅助作用

int      mlik[MAXN];         //很关键,与其邻接但未删除顶点地最小访问时间

int      indx[MAXN];         //顶点访问时间

AdjTable adj[MAXN];          //邻接表

 

//深搜过程,该算法的主体都在这里

void Visit(int cur, int &sig, int &scc_num)

{

   int  i;

 

   stck[++stck[0]] = cur; flag[cur] = VIS;

   mlik[cur] = indx[cur] = ++sig;

 

   for ( i=1; i<=adj[cur][0]; ++i )

   {

      if ( NOTVIS==flag[adj[cur][i]] )

      {

          Visit(adj[cur][i],sig,scc_num);

          if ( mlik[cur]>mlik[adj[cur][i]] )

          {

             mlik[cur] = mlik[adj[cur][i]];

          }

      }

      else if ( VIS==flag[adj[cur][i]] )

      {

          if ( mlik[cur]>indx[adj[cur][i]] )  //该部分的indx应该是mlik,但是根据算法的属性,使用indx也可以,且时间更少

          {

             mlik[cur] = indx[adj[cur][i]]; 

          }

      }

   }

 

   if ( mlik[cur]==indx[cur] )

   {

      ++ scc_num;

      do

      {

          belg[stck[stck[0]]] = scc_num;

          flag[stck[stck[0]]] = OVER;

      }

      while ( stck[stck[0]--]!=cur );   

   }

}

 

//Tarjan算法,求解belg[1..n],且返回强连通分量个数,

int Tarjan_StronglyConnectedComponent()

{

   int  i, sig, scc_num;

 

   memset(flag+1,NOTVIS,sizeof(char)*n);

 

   sig = 0; scc_num = 0; stck[0] = 0;

   for ( i=1; i<=n; ++i )

   {

      if ( NOTVIS==flag[i] )

      {

          Visit(i,sig,scc_num);

      }

   }

 

   return scc_num;

} 

 

三、   Gabow算法

1.      思路分析

这个算法其实就是Tarjan算法的变异体，我们观察一下，只是它用第二个堆栈来辅助求出强连通分量的根，而不是Tarjan算法里面的indx[]和mlik[]数组。那么，我们说一下如何使用第二个堆栈来辅助求出强连通分量的根。

我们使用类比方法，在Tarjan算法中，每次mlik[i]的修改都是由于环的出现(不然，mlik[i]的值不可能变小)，每次出现环，在这个环里面只剩下一个mlik[i]没有被改变(深度最低的那个)，或者全部被改变，因为那个深度最低的节点在另一个环内。那么Gabow算 法中的第二堆栈变化就是删除构成环的节点，只剩深度最低的节点，或者全部删除，这个过程是通过出栈来实现，因为深度最低的那个顶点一定比前面的先访问，那 么只要出栈一直到栈顶那个顶点的访问时间不大于深度最低的那个顶点。其中每个被弹出的节点属于同一个强连通分量。那有人会问：为什么弹出的都是同一个强连 通分量？因为在这个节点访问之前，能够构成强连通分量的那些节点已经被弹出了，这个对Tarjan算法有了解的都应该清楚，那么Tarjan算法中的判断根我们用什么来代替呢？想想，其实就是看看第二个堆栈的顶元素是不是当前顶点就可以了。

现在，你应该明白其实Tarjan算法和Gabow算法其实是同一个思想的不同实现，但是，Gabow算法更精妙，时间更少(不用频繁更新mlik[])。 

2.      伪代码

Gabow_Algorithm:

           step1:

     找一个没有被访问过的节点v，goto step2(v)。否则，算法结束。

           step2(v):

            将v压入堆栈stk1[]和stk2[]

            对于v所有的邻接顶点u：

  1)     如果没有访问过，则step2(u)

  2)     如果访问过，但没有删除，维护stk2[](处理环的过程)

            如果stk2[]的顶元素==v，那么输出相应的强连通分量 

3.      实现代码

#include <iostream>

using namespace std;

 

const int MAXN = 110;

 

typedef int AdjTable[MAXN]; //邻接表类型

 

int      n;

int      intm[MAXN]; //标记进入顶点时间

int      belg[MAXN]; //存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量

int      stk1[MAXN]; //辅助堆栈

int      stk2[MAXN]; //辅助堆栈

AdjTable adj[MAXN]; //邻接表

 

//深搜过程,该算法的主体都在这里

void Visit(int cur, int &sig, int &scc_num)

{

   int  i;

 

   intm[cur] = ++sig;

   stk1[++stk1[0]] = cur;

   stk2[++stk2[0]] = cur;

 

   for ( i=1; i<=adj[cur][0]; ++i )

   {

      if ( 0==intm[adj[cur][i]] )

      {

          Visit(adj[cur][i],sig,scc_num);

      }

      else if ( 0==belg[adj[cur][i]] )

      {

          while ( intm[stk2[stk2[0]]]>intm[adj[cur][i]] )

          {

             -- stk2[0];

          }

      }

   }

 

   if ( stk2[stk2[0]]==cur )

   {

      -- stk2[0]; ++ scc_num;

      do

      {

          belg[stk1[stk1[0]]] = scc_num;

      }

      while ( stk1[stk1[0]--]!=cur );

   }  

}

 

//Gabow算法,求解belg[1..n],且返回强连通分量个数,

int Gabow_StronglyConnectedComponent()

{

   int  i, sig, scc_num;

 

   memset(belg+1,0,sizeof(int)*n);

   memset(intm+1,0,sizeof(int)*n);

   sig = 0; scc_num = 0; stk1[0] = 0; stk2[0] = 0; 

   for ( i=1; i<=n; ++i )

   {

      if ( 0==intm[i] )

      {

          Visit(i,sig,scc_num);

      }

   }

 

   return scc_num;

} 

 

 

    写到这里，做一个总结：Kosaraju算法的第二次深搜隐藏了一个拓扑性质，而Tarjan算法和Gabow算法省略了第二次深搜，所以，它们不具有拓扑性质。Tarjan算法用堆栈和标记，Gabow用两个堆栈（其中一个堆栈的实质是代替了Tarjan算法的标记部分）来代替Kosaraju算法的第二次深搜，所以只用一次深搜，效率比Kosaraju算法高。

╝⑤

 

 

§5问题归约

╔

最大流归约

 

1.允许多源点和多汇点或增加顶点容量约束的流网络，其最大流问题等价于标准最大流问题（前面讲解的情况就是标准最大流问题）。

如对于顶点容量约束我们可以用顶点u和u*对于原来顶点u，边<u,u*>的容量就是顶点u的容量。

2.无环网的最大流问题等价于标准最大流问题。

无环网改造成多源点和多汇点最大流问题。

3.可行流问题可归约到最大流问题。

可行流

假设在一个流网络中为每一个顶点赋予一个全职，并将此解释为供应（正）或需求（负），而且顶点权值之和为0，可行流可以定义为每个顶点的流出量与流入量之差等于那个顶点的权值。给定一个这样的网，确定是否存在一个可行流。

4.最大基数二分匹配问题可以归约到最大流的可行流。

最大基数二分匹配

给定一个二分图，找出最大基数的一个边集，满足每个顶点至多连接到一个其他顶点。

5.二分图问题可归约到最大流问题。

给定一个二分图问题，通过为所有边指定从一个集合到另一集合的方向，并添加一个源点以及该源点指向二分图中其中一个集合的所有顶点的边，在如此添加一个汇点到另一个集合。每条边的容量为1。

6.（Menger定理）在有向图中删除某条边是两个顶点不连通的最少边等于这两个顶点之间边不相交的路径的最大数目。

给定一个有向图，用同一组顶点和边定义一个网络，其中所有边的容量均定义为1，任何一个从s到t的边不相交的路径数目等于流值。

 

最小成本流归约

 

1.（无负环的）单源点最短路径问题可归约为最小成本可行流问题。

2.分配问题，邮差问题，运输问题等价于最小成本流问题。

╝⑥

 

 

 

 

§6小结

 

本文粗略地介绍了有向强连通求解和网络流大讲堂——求解最大流（最小割）、最小费用最大流的相关知识，虽然还没有最终完工，由于一直放不下心总想完成，但又苦于没有大量时间去学习，就先暂且搁浅（草草结束这篇文章的相关理论的整理和写作），日后有闲暇定当完成。如果你有任何建议或者批评和补充，请留言指出，不胜感激，更多参考请移步互联网。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

参考

①plussai： http://plussai.iteye.com/blog/1128127

②'wind： http://www.cnblogs.com/dream-wind/archive/2012/03/15/2397192.html

③

Hao的博客： http://chhaj5236.blog.163.com/blog/static/11288108120099725027512/

④_Never_： http://www.cnblogs.com/fornever/archive/2011/09/20/2182903.html

⑤http://www.cppblog.com/koson/archive/2010/04/27/113694.html

⑥Robert Sedgewick: Algorithm in C

 

 

 

 

 

 

 

 

 

 

 

 

评论

1 楼 一样的追寻 2016-12-09  

感谢楼主！