Network flow learning notes

One 、 Basic concepts

1. Network flow problem

Given a given directed graph , There are two special points Source point S And meeting point T, Each side has a specified capacity , In order to satisfy the condition S To T The maximum flow of .

Generally speaking ： The source can be regarded as a waterworks , Meeting point can be regarded as your home
Then a lot of water pipes were built between the waterworks and your home , The maximum capacity of water pipes is different （ Super , The water pipe will explode ）
then Ask the water plant to open the gate to deliver water , What is the maximum flow of water your home receives
If the water plant stops running , Then your traffic is 0, This is definitely not the maximum flow
But if you set up a water plant VIP card , The water plant desperately supplies water , But your home traffic will reach a value and will not change , At this time, the maximum flow is reached .

2. Three basic properties

For any moment , set up f(u,v) Actual flow rate ,c(u,v) The maximum capacity , Then the whole picture G Six networks meet 3 Nature ：

1. Capacity limit ： To any u,v∈V,f(u,v) <= c(u,v).
2. Antisymmetry ： To any u,v∈V,f(u,v) = -f(v,u). from u To v The flow must be from v To u The opposite value of the flow .（ It can be compared with one-dimensional displacement in Physics ）
3. Conservation of flow ： For any u, if u Not for s perhaps t, There must be ∑f(u,v) = 0,(u,v)∈E. namely u The sum of traffic to adjacent nodes is 0, Because inflow u Traffic and u The outflow flow is the same ,u It's just traffic “ hamal ”.

3. Capacity network Traffic network Residual network

• network ： Digraph of active point and sink point , The network of what refers to the meaning of the edge weight representation in the directed graph
• Capacity network ： Network about capacity , Basically unchanged （ Very few problems need to be changed ）
• Traffic network ： Network about traffic , In the process of solving the problem , It's always changing , But it always satisfies the above three properties , The final adjustment is the maximum flow network , At the same time, the maximum flow value can also be obtained
• Residual network ： Residual network = Capacity network - Traffic network （ Always established ）, But the residual network may be larger than the capacity network

4. cut Cut set

• Cut set of undirected graph ：C[A,B] It refers to the graph G It is divided into A and B Two point sets A and B The complete set of edges between
• Cut set of network ：C[S,T] It refers to the ability to connect the network G It is divided into S and T Two point sets （s Belong to S And t Belong to T） From the s To t The complete set of edges of
• Cut of weighted graph ： The sum of weights of edges or directed edges in a cut set

Popular said ：
Cutting sets is like someone cutting off some of the water pipe network from the water plant to your home
then , Your family can't receive tap water from the water plant
This person will care about the size of the cut , After all, the fine water pipe is easier to cut , And the minimum cutting takes the least effort .

Two 、 Maximum flow basic algorithm

Template title ：https://www.luogu.com.cn/problem/P3376

1.FF Algorithm （Ford-Fullkerson）（ Augment the way ）

Augmented path method is the basis of many network flows , Generally, it is implemented in the residual network
The idea ： Find a path that can increase the flow from the source point to the sink point every time , Adjust the flow value and residual network , Constantly adjust to know that there is no Zengguang road .
FF The basis of the algorithm is the augmented path theorem ： The network reaches the maximum flow if and only until there is no augmented path in the residual network .
Remember that the maximum flow is F ,FF The algorithm can be carried out at most F Time DFS, Time complexity ：O(F|E|), This is a very loose upper bound , There is almost no case for this worst-case complexity .

// A structure used to represent edges （ End , Capacity , Reverse side ）
struct edge{
    
    int to,cap,rev;
};
vector<edge> G[maxn];
bool used[maxn];	//DFS Access tags used in 
// Add a line from  from  To  to  Capacity of  cap  The edge of 
void add(int from,int to,int cap)
{
    
    G[from].push_back((edge){
    to,cap,G[to].size()});
    G[to].push_back((edge){
    from,0,G[from].size()-1});
}
// adopt DFS Looking for a way to expand 
int dfs(int v,int t,int f)
{
    
    if(v==t)    return f;
    used[v] = true;
    for(int i=0;i<G[v].size();i++){
    
        edge &e = G[v][i];
        if(!used[e.to]&&e.cap>0){
    
            int d = dfs(e.to,t,min(f,e.cap));
            if(d>0){
    
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}
// The solution comes from  s  To  t  The maximum flow of 
int max_flow(int s,int t)
{
    
    int flow = 0;
    for( ; ; ){
    
        memset(used,0,sizeof(used));
        int f = dfs(s,t,INF);
        if(f==0)    return flow;
        flow += f;
    }
}

Dinic Algorithm

It's described above FF The algorithm is to find the augmented path by depth first searching , And expand along it . In contrast ,Dinic The algorithm always looks for the shortest augmented path , And expand along it . because The length of the shortest augmentation path is always the same in the augmentation process , Therefore, it is not necessary to search for the shortest augmented path through width pre search every time .
Let's start with a width first search , Then consider a hierarchical graph composed of edges from near points to distant vertices , Do a depth first search on it to find the shortest augmented path .
If you can't find a new augmented Road on the layered map , It shows that the length of the shortest augmented road has indeed increased , That is, there is no shortest augmentation path , Then a new hierarchical graph is constructed through width first search .
Time complexity ：O(|E||V|²)
Code after arc optimization and multi-channel augmentation ：

// A structure used to represent edges （ End , Capacity , Reverse side ）
struct edge{
    
    int to,cap,rev;
};
vector<edge> G[maxn];
int level[maxn];    // Distance label from vertex to source 
int iter[maxn];		// Current arc , The side before it is useless 
// Add a line from  from  To  to  Capacity of  cap  The edge of 
void add(int from,int to,int cap)
{
    
    G[from].push_back((edge){
    to,cap,G[to].size()});
    G[to].push_back((edge){
    from,0,G[from].size()-1});
}
// adopt BFS Calculate the distance label from the origin 
void bfs(int s)
{
    
    memset(level,-1,sizeof(level));
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while(!que.empty()){
    
        int v = que.front();
        que.pop();
        for(int i=0;i<G[v].size();i++){
    
            edge &e = G[v][i];
            if(e.cap>0&&level[e.to]<0){
    
                level[e.to] = level[v] + 1;
                que.push(e.to);
            }
        }
    }
}
// adopt DFS Looking for a way to expand 
int dfs(int v,int t,int f)
{
    
    if(v==t)    return f;
    for(int &i=iter[v];i<G[v].size();i++){
    
        edge &e = G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
    
            int d = dfs(e.to,t,min(f,e.cap));
            if(d>0){
    
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}
// The solution comes from  s  To  t  The maximum flow of 
int max_flow(int s,int t)
{
    
    int flow = 0;
    for( ; ; ){
    
        bfs(s);
        if(level[t]<0)  return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while((f=dfs(s,t,INF))>0){
    
            flow += f;
        }
    }
}

Highest grade preflow propulsion （HLPP）：

Reference from ：https://www.cnblogs.com/owenyu/p/6858123.html

Example ：https://loj.ac/problem/127

Preflow propulsion is a very intuitive network flow algorithm . If you are given a network flow, let you calculate it by hand , The general idea is to start from the source , If there is not enough, reduce , Push straight ahead to the meeting point . This is the basic idea of the preflow propulsion Algorithm .

Each node is a reservoir , At first, there is infinite water at the source . Maintain the points to be processed with a queue . At first, add the source point , For each current point , Let's take the flow in the pool at this point along the side （ Water pipe ） Push to the adjacent point , Then add the adjacent points to the queue .

The idea of algorithm is like this , But there is one problem ： In this way, there may be two points, one pushed forward and the other pushed back , The result is a dead cycle . At this time, we introduce a height to each point to solve this problem .

The height of the source point is n, The height of the meeting point is 0, The initial height of other points is 0, Our rules , Water flows down a layer , That is, we only push level[x] = level[v] + 1 The edge of (x,v).

If there is still water at one point , But it can't be pushed out , That is, the surrounding points are higher than him , Then let's raise this point , because h Values are continuous , So every time this happens, we add one to it . If this point cannot flow out at all , Then eventually it will be raised to n+1 Height , Return to the source .

Time complexity ：O(n²$\sqrt{m}$)

struct edge{
    
    int to,cap,rev;
};
vector<edge> G[maxn];
int level[maxn],gap[maxm],ep[maxn];
bool inq[maxn];
int n,m,s,t;
struct cmp{
    
    bool operator()(int a,int b) const{
    
        return level[a] < level[b];
    }
};
priority_queue<int, vector<int>, cmp> q;
void add(int from, int to, int cap){
    
    G[from].push_back((edge){
     to, cap, G[to].size() });
    G[to].push_back((edge){
     from, 0, G[from].size() - 1 });
}
bool bfs(){
    
    queue<int> que;
    memset(level,inf,sizeof(level));
    level[t] = 0;
    que.push(t);
    while(!que.empty()){
    
        int v = que.front();
        que.pop();
        for(int i=0;i<G[v].size();i++){
    
            edge &e = G[v][i];
            if(G[e.to][e.rev].cap>0&&level[e.to]>level[v]+1){
    
                level[e.to] = level[v] + 1;
                que.push(e.to);
            }
        }
    }
    return level[s] != inf;
}
void push_flow(int v)
{
    
    for(int i=0;i<G[v].size();i++){
    
        edge &e = G[v][i];
        if(e.cap>0&&level[e.to]+1==level[v]){
    
            int f = min(ep[v],e.cap);
            e.cap -= f;G[e.to][e.rev].cap += f;
            ep[v] -= f;ep[e.to] += f;
            if(e.to!=s&&e.to!=t&&!inq[e.to]){
    
                q.push(e.to);
                inq[e.to] = true;
            }
            if(!ep[v])  break;
        }
    }
}
void reset(int v)
{
    
    level[v] = inf;
    for(int i=0;i<G[v].size();i++){
    
        edge &e = G[v][i];
        if(e.cap&&level[e.to]+1<level[v]){
    
            level[v] = level[e.to] + 1;
        }
    }
}
int hlpp(){
    
    if(!bfs())  return 0;
    level[s] = n;
    memset(gap,0,sizeof(gap));
    for(int i=1;i<=n;i++){
    
        if(level[i]<inf)   gap[level[i]]++;
    }
    for(int i=0;i<G[s].size();i++){
    
        edge &e = G[s][i];
        if(e.cap){
    
            int pas = e.cap;
            e.cap -= pas;G[e.to][e.rev].cap += pas;
            ep[s] -= pas;ep[e.to] += pas;
            if(e.to!=s&&e.to!=t&&!inq[e.to]){
    
                q.push(e.to);
                inq[e.to] = true;
            }
        }
    }
    while(!q.empty()){
    
        int pas = q.top();
        inq[pas] = false;
        q.pop();
        push_flow(pas);
        if(ep[pas]){
    
            gap[level[pas]]--;
            if(!gap[level[pas]]){
    
                for(int i=1;i<=n;i++){
    
                    if(i!=s&&i!=t&&level[i]>=level[pas]&&level[i]<n+1){
    
                        level[i] = n + 1;
                    }
                }
            }
            reset(pas);
            gap[level[pas]]++;
            q.push(pas);
            inq[pas] = true;
        }
    }
    return ep[t];
}