[network flow] maximum flow: algorithm template, bipartite graph matching

Algorithm template

Time complexity of Ek algorithm: O(nm2)O(nm^2)O(nm2)

Give a flow network and maintain the residual network.

while(){
	①Find Zengguang road in the current residual network(bfs):f'
	②Update residual network:Put the current residual network Gf Residual network updated to new stream G(f+f')
} 

① Simple traversal, bfsbfsbfs can be used.

② Suppose that the capacity of the forward side in the current residual network is c1c_1c1, the capacity of the reverse side is c2c_2c2, and the expanded path flows kkk flow, and the capacity of the forward side becomes c1 − kc_1-kc1 − K, the capacity of the reverse side becomes c2+kc_2+kc2​+k.

Update: once an augmented path from sss to ttt is found, first consider how many streams can be added to the entire augmented path, that is, the traffic on the smallest side. If the flow of the smallest edge is kkk, then the flow of the whole augmented path is kkk, and then update the capacity of all edges on this path in the way described above.

Use pre[]pre[]pre [] to record the leading edge, and the whole path can be recorded.

  • Ekekek algorithm is generally not used in finding the maximum flow, but ekek algorithm is a core algorithm in finding the minimum cost flow.

How to save a map
Use adjacency table. In order to quickly find the reverse edge of each edge, it can be stored in pairs, that is, the second edge stores the reverse edge of the first edge, and the fourth edge stores the reverse edge of the third edge.

Original question link

The code is as follows:

#include<bits/stdc++.h>
using namespace std;

const int N=1000+10;
const int M=20000+10;
const int INF=1e9;

int n,m,S,T;
int h[N],ve[M],c[M],ne[M],id;
int q[N],d[N]/*Record the minimum capacity of all current edges*/,pre[N];
bool v[N];//Weight judgment to avoid repeated search

void add(int x,int y,int z){//Maintaining a residual network
    ve[id]=y;c[id]=z;ne[id]=h[x];h[x]=id++;
    ve[id]=x;c[id]=0;ne[id]=h[y];h[y]=id++;
}

bool bfs(){//Find Zengguang Road
    memset(v,0,sizeof v);
    int he=0,ta=0;
    q[0]=S;v[S]=1;d[S]=INF;
    
    while(he<=ta){
        int x=q[he++];
        
        for(int i=h[x];~i;i=ne[i]){
            int y=ve[i];
            
            if(!v[y]&&c[i]){
                v[y]=1;
                d[y]=min(d[x],c[i]);
                pre[y]=i;//Number of leading edge of recording point y
                
                if(y==T)return true;//Find augmentation path
                q[++ta]=y;
            }
        }
    }
    return false;
}

int EK(){
    int ans=0;
    while(bfs()){//Find an augmentation path and update the residual network
        ans+=d[T];
        
        for(int i=T;i!=S;i=ve[pre[i]^1]){
            c[pre[i]]-=d[T];c[pre[i]^1]+=d[T];
        }
    }
    
    return ans;
}

int main(){
    scanf("%d%d%d%d",&n,&m,&S,&T);
    memset(h,-1,sizeof h);
    
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    
    printf("%d",EK());
    return 0;
}

Dinic algorithm time complexity: O(n2m)O(n^2m)O(n2m)

On the basis of ekek algorithm, the idea of layered graph is added, that is, not only one path is widened each time, but many paths are widened. DinicDinicDinic algorithm is the optimization of EKEKEK algorithm.

Algorithm flow of finding Zengguang Road:

① bfsbfsbfs build layered map.

② Search all the paths that can be widened in the figure through dfsdfs and expand them uniformly.

The maintenance is the residual network.

You need to optimize with the current arc. That is: when an edge of the current point is full, skip this edge and search for the next edge.

Original question link

The code is as follows:

#include<bits/stdc++.h>
using namespace std;

const int N=10000+10;
const int M=200000+10;
const int INF=1e9;

int n,m,S,T;
int h[N],ve[M],c[M],ne[M],id;
int q[N],d[N],cur[N]/*Current arc optimization*/;

void add(int x,int y,int z){
    ve[id]=y;c[id]=z;ne[id]=h[x];h[x]=id++;
    ve[id]=x;c[id]=0;ne[id]=h[y];h[y]=id++;
}

bool bfs(){//Find Zengguang road and build layered map
    int he=0,ta=0;
    memset(d,-1,sizeof d);
    q[0]=S;d[S]=0;cur[S]=h[S];
    
    while(he<=ta){
        int x=q[he++];
        
        for(int i=h[x];~i;i=ne[i]){
            int y=ve[i];
            
            if(d[y]==-1&&c[i]){
                d[y]=d[x]+1;//Establish hierarchical map
                cur[y]=h[y];//The current arc of the current point is the first edge
                if(y==T)return true;
                q[++ta]=y;
            }
        }
    }
    return false;
}

int dfs(int u,int limit){//Search from point u, and the maximum flow from s to u is limit
    if(u==T)return limit;
    int flow=0;//Maximum flow from u to t
    
    for(int i=cur[u]/*Search from the currently under filled path*/;~i&&flow<limit;i=ne[i]){
        cur[u]=i;//Record the current search arc (current arc optimization)
        int y=ve[i];
        
        if(d[y]==d[u]+1&&c[i]){
            int t=dfs(y,min(c[i],limit-flow));
            if(!t)d[y]=-1;//If the current edge is not available, the point is deleted
            c[i]-=t;c[i^1]+=t;flow+=t;
        }
    }
    
    return flow;
}

int dinic(){
    int ans=0,flow;
    
    while(bfs())//Zengguang Road
        while(flow=dfs(S,INF))//Search all augmented paths in the current residual network
            ans+=flow;//Add the total flow that can be added
    
    return ans;
}

int main(){
    scanf("%d%d%d%d",&n,&m,&S,&T);
    memset(h,-1,sizeof h);
    
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    
    printf("%d",dinic());
    return 0;
}

Bipartite graph matching

Pilot pairing scheme problem

Original question link

Give a bipartite graph and find out how many matches there are at most. The requirement is that each point can only be in one match, and the scheme can be output at the same time.

From the data range, we can know that there is no problem with Hungarian algorithm. However, this article uses maximum flow to solve this problem.

  • First consider how to create a drawing:

① Connect an edge with a capacity of 111 from sss to each point in the first point set (i.e. foreign pilots).

② Connect an edge with a capacity of 111 to ttt from each point in the second point set (i.e. British pilots).

③ For the edge between two point sets, connect an edge with a capacity of 111 from the first point set to the second point set.

  • Next, consider whether the set {f}\{f\}{f} of feasible flows of such a network GGG corresponds to the set {s} \ {s} of solutions of the original PPP problem one by one.

Note: {f}\{f\}{f} is not a set of all feasible flows, but a set of all integer feasible flows.

① Proof S ⇒ fS \ Rightarrow fS ⇒ f, that is, the feasible solution of the original problem is the feasible flow in the flow network.

The connected edge of the graph is a feasible edge, as shown in the solution. Record the flow of the connected side as 111.

(i) Considering the flow conservation: the flow from sss is 444, the flow into ttt is 444, and the flow into and out of all connected points except s, TS, TS and t is 111.

(ii) consider capacity constraints: obviously.

Therefore, the feasible solution of the original problem can be transformed into a feasible flow in the flow network.

② Proof f ⇒ Sf \ Rightarrow Sf ⇒ S, that is, the feasible flow in the flow network is the feasible solution of the original problem.

Firstly, a feasible flow in the outflow network is constructed at will.

For the first point set, the flow of each point must be the flow from sss. When constructing the flow network, each point in the first point set has only one edge connected with sss, that is, the maximum flow of each point in the first point set is 111. According to the flow conservation, the flow from each point in the first point set is also 111, that is, any point in the first point set can only match a point in the second point set.

For the second point set, the flow from each point must be the flow into ttt. When constructing the flow network, only one edge of each point in the second point set is connected to ttt, that is, the maximum flow from each point in the second point set is 111. According to the flow conservation, the flow into each point in the second point set is also 111, that is, any point in the second point set can only match a point in the first point set.

To sum up, any point in each group of points matching the first point set and the second point set will no longer match other points. Meet the requirements of feasible solution in the original problem.

Therefore, a feasible flow in the flow network can be transformed into a feasible solution in the original problem.

Therefore, the maximum flow of the constructed flow network is the maximum matching in the original problem.

Time complexity: if Hungarian algorithm is used, it is O(nm)O(nm)O(nm); If dinicdinic algorithm is used, it is O(mn)O(m\sqrt{n})O(mn).

How to find a scheme: that is, the mapping process. Enumerate all the edges in the middle to see which edge has full traffic. The edge with full traffic is a match.

The code is as follows:

#include<bits/stdc++.h>
using namespace std;

const int N=100+10;
const int M=6000+10;
const int INF=1e9;

int n,m,S,T;
int h[N],ve[M],c[M],ne[M],id;
int q[N],d[N],cur[N];

void add(int x,int y,int z){
    ve[id]=y;c[id]=z;ne[id]=h[x];h[x]=id++;
    ve[id]=x;c[id]=0;ne[id]=h[y];h[y]=id++;
}

bool bfs(){
    int he=0,ta=0;
    memset(d,-1,sizeof d);
    q[0]=S;d[S]=0;cur[S]=h[S];
    
    while(he<=ta){
        int x=q[he++];
        
        for(int i=h[x];~i;i=ne[i]){
            int y=ve[i];
            
            if(d[y]==-1&&c[i]){
                d[y]=d[x]+1;
                cur[y]=h[y];
                if(y==T)return true;
                q[++ta]=y;
            }
        }
    }
    return false;
}

int dfs(int u,int limit){
    if(u==T)return limit;
    
    int flow=0;
    for(int i=h[u];~i&&flow<limit;i=ne[i]){
        cur[u]=i;
        int y=ve[i];
        if(d[y]==d[u]+1&&c[i]){
            int t=dfs(y,min(c[i],limit-flow));
            if(!t)d[y]=-1;
            c[i]-=t;c[i^1]+=t;flow+=t;
        }
    }
    
    return flow;
}

int dinic(){
    int ans=0,flow;
    
    while(bfs())
        while(flow=dfs(S,INF))
            ans+=flow;
            
    return ans;
}

int main(){
    scanf("%d%d",&m,&n);
    S=0;T=n+1;
    memset(h,-1,sizeof h);
    
    for(int i=1;i<=m;i++)
        add(S,i,1);
        
    for(int i=m+1;i<=n;i++)
        add(i,T,1);
        
    int x,y;
    while(1){
        scanf("%d%d",&x,&y);
        if(x==-1&&y==-1)break;
        
        add(x,y,1);
    }
    
    printf("%d\n",dinic());
    
    //Search scheme
    for(int i=0;i<id;i+=2)//Enumerate even numbered edges (positive edges) if any
        if(ve[i]>m&&ve[i]<=n&&!c[i])//Judge whether the current edge is in the middle position, and the edge is full flow
            printf("%d %d\n",ve[i^1],ve[i]);
    
    return 0;
}

Round table questions

mmm units can be regarded as a point set with mmm points, and nnn round tables can be regarded as a point set with nnn points. It is obviously a bipartite graph matching problem, but different from the general bipartite graph matching problem, each point can be selected multiple times. Therefore, this problem is called bipartite graph multiple matching problem.

Drawing construction: similar to the drawing construction in the above figure.

① From sss to each point in the first point set (i.e. unit), connect an edge with the capacity of the representative number of the corresponding unit.

② Connect an edge with the capacity of the corresponding round table to ttt from each point in the second point set (i.e. round table).

③ For the edge between two point sets, connect an edge with a capacity of 111 from the first point set to the second point set.

  • Next, consider whether the set {f}\{f\}{f} of feasible flows of such a network GGG corresponds to the set {s} \ {s} of solutions of the original PPP problem one by one.

① Proof S ⇒ fS \ Rightarrow fS ⇒ f, that is, the feasible solution of the original problem is the feasible flow in the flow network.

First, select some middle edges at will:

Assign the flow of all selected edges to 111.

From sss to the first point set: each unit sends several people, and the traffic is a few.

From the second point set to ttt: how many people will sit in each round table, and how many people will flow.

Check whether it is a feasible flow of the flow network.


Check whether the flow is feasible, that is, check whether the two properties of feasible flow are true.

(i) Capacity limit:

The maximum flow of all sides in the middle is 111, and the capacity is 111, which is satisfied.

For each side on the left: because the scheme is legal, the number of Representatives (i.e. flow) sent by each unit must not exceed the number of Representatives (i.e. capacity) of each unit.

Similarly, the right side also meets the capacity limit.

(ii) flow conservation:

Similarly, because the scheme is legal, the flow conservation is also satisfied.

Therefore, any feasible solution of the original problem can construct a feasible flow in the flow network.

② Proof f ⇒ Sf \ Rightarrow Sf ⇒ S, that is, the feasible flow in the flow network is the feasible solution in the original text.

Since the capacity of the middle side is 111, each unit can send up to one representative to each round table. In line with the meaning of the topic.

Because the capacity of the left side is the maximum number of people in a unit, the flow cannot exceed the total number of people (i.e. capacity).

Similarly, the right side also conforms to the meaning of the question.

Therefore, any feasible flow in the flow network corresponds to a feasible solution in the original problem.

  • Seek a legal plan so that all delegates have round tables.

Therefore, all the edges starting from sss are full flow. The original problem is to find the maximum flow of the original network and verify whether the maximum flow is equal to the total number of people. If it is equal to the total number of people, it is a legal scheme; If not, the original problem has no solution.

Therefore, the original problem can be transformed into a maximum flow problem.

Output scheme: see which side in the middle is full.

The code is as follows:

using namespace std;

const int N=500+10;
const int M=1000000+10;
const int INF=1e9;

int n,m,S,T;
int h[N],ve[M],c[M],ne[M],id;
int q[N],d[N],cur[N];

void add(int x,int y,int z){
    ve[id]=y;c[id]=z;ne[id]=h[x];h[x]=id++;
    ve[id]=x;c[id]=0;ne[id]=h[y];h[y]=id++;
}

bool bfs(){
    int he=0,ta=0;
    memset(d,-1,sizeof d);
    q[0]=S;d[S]=0;cur[S]=h[S];
    
    while(he<=ta){
        int x=q[he++];
        
        for(int i=h[x];~i;i=ne[i]){
            int y=ve[i];
            
            if(d[y]==-1&&c[i]){
                d[y]=d[x]+1;
                cur[y]=h[y];
                if(y==T)return true;
                q[++ta]=y;
            }
        }
    }
    return false;
}

int dfs(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    
    for(int i=cur[u];~i&&flow<limit;i=ne[i]){
        cur[u]=i;
        int y=ve[i];
        
        if(d[y]==d[u]+1&&c[i]){
            int t=dfs(y,min(c[i],limit-flow));
            if(!t)d[y]=-1;
            c[i]-=t;c[i^1]+=t;flow+=t;
        }
    }
    return flow;
}

int dinic(){
    int ans=0,flow;
    
    while(bfs())
        while(flow=dfs(S,INF))
            ans+=flow;
            
    return ans;
}

int main(){
    scanf("%d%d",&m,&n);
    S=0;T=m+n+1;
    memset(h,-1,sizeof h);
    
    int tot=0;
    for(int i=1;i<=m;i++){
        int x;scanf("%d",&x);
        add(S,i,x);
        
        tot+=x;
    }
    
    for(int i=m+1;i<=m+n;i++){
        int x;scanf("%d",&x);
        add(i,T,x);
    }
    
    for(int i=1;i<=m;i++)
        for(int j=m+1;j<=m+n;j++)
            add(i,j,1);
            
    if(dinic()!=tot)puts("0");
    else{
        puts("1");
        for(int i=1;i<=m;i++){
            for(int j=h[i];~j;j=ne[j])
                if(ve[j]>m&&ve[j]<=m+n&&!c[j])
                    printf("%d ",ve[j]-m);
            
            puts("");        
        }
    }
    
    return 0;
}

Tags: Graph Theory

Posted by caraldur on Wed, 25 May 2022 10:15:55 +0300