dinic(数组)

 

    一直想学dinic算法，但是没找到好的资料，看了《网络流》感觉这书太好了，感觉加深了对网络流的理解，先学了SAP算法，然后就是Dinic算法。 其实2者差不多。

     Dinic算法的实质是在层次图里找最短增广路进行增广， 通过BFS构造层次图，然后采用SAP的算法，但是有3点改进：

    1.we do not change the distance label of node i, but subsequently tern node i is blocked, A blocked node has no admissible path to the sink node.

    2.：we define an arc (i,j) to be admissible if d[i] = d[j] + 1 r[i][j] > 0 and j is not blocked.

    3.When the source node is blocked, by performing a BFS we recompute the distance labels of all nodes exactly.

    其他就和SAP一样就行了。

#include
#include
#include
using namespace std;
const int MAX = 225;
const int oo  = 2100000000;
int n,m,c[MAX][MAX],remain[MAX][MAX],source,sink,nc,np        //remain为剩余图，又名残留网络
int dis[MAX],block[MAX];
void bfs()                            //bfs建立层次图,即用数组dis[]记录各个结点的深度
{
    int q[MAX],head=0,tail=0,u,v;
    for(int i=0;i<=sink;i++)
        dis[i]=oo;
    q[++head]=sink;
    dis[sink]=0;
    while(tail < head)
    {
        u = q[++tail];    //出队
        for(v=0;v<=sink;v++)
            if(dis[v] ==oo && remain[v][u]>0)
            {
                dis[v]=dis[u]+1;
                q[++head]=v;
            }
    }
}
//dfs搜索增益路径,dinic == dfs
int dinic()
{
    bfs();                            //之后source在最后一层
    int top = source,pre[MAX],flow=0;            //top是最短增广路最前面一个节点,pre保存路径,同时作为dfs堆栈
    int i,j,k,low[MAX];
    memset(low,0,sizeof(low));
    memset(block,0,sizeof(block));
    //下为dfs标准过程
    while(dis[source]!=oo)                    //dinic算法结束条件：从源点到汇点没有路,终点sink为第0层
    {
        bool flag = false;
        low[source]=oo;
        for(i=0;i<=sink;i++)                //在top的邻接边中找容许边
            if(remain[top][i]>0 && dis[top]==dis[i]+1 && !block[i])
            {
                flag = true;
                break;
            }
        if(flag)                    //如果找到
        {
            low[i] = remain[top][i];            //low 保存当前节点的最小容量,且终点sink的最小容量为路径流量
            if(low[i] > low[top])
                low[i]=low[top];         //更新
            pre[i] = top;top=i;


            if(top == sink)                //找到路
            {
                flow += low[sink];
                j = top;
                while(j != source)        //回溯更新(剩余图)残留网络remain[max][max]
                {
                    k = pre[j];
                    remain[k][j]-=low[sink];
                    remain[j][k]+=low[sink];
                    j = k;
                }
                top = source;             //准备下一循环,重新找增广路
                memset(low,0,sizeof(low));
            }


        }
        else                        //无容许边存在，则阻塞当前点
        {
            block[top] = 1;
            if(top != source)
                top = pre[top];            //非源点阻塞就回溯,继续dfs
            else                    //如果源点阻塞了就重新建立层次图
            {
                bfs();
                memset(block,0,sizeof(block));
            }
        }
    }
    return flow;
}
main()
{
    
}