This blog is an article I wrote about learning network flow in my second year of high school. It was originally posted on Luogu, and the response was good. As the first article, it was posted on CSDN to test the water.
What is network flow?
Give you a directed graph to represent the flow direction of various water pipes from the water tower to your home, and the side indicates how many liters of water the water pipe can pass through in one second. How many liters of water can flow inside.
That is, the flow problem on the network diagram.
Note that the water tower mentioned here is the source, and the faucet is the sink.
For example, the maximum flow of this picture is 19 19 19 (Think about why.
It is easy to find that if we are a program (you can imagine it yourself, no need to practice, just kidding), then solving the maximum flow seems to be greedy in my eyes, as long as it is a pipeline that can flow, I can directly flow it, nothing more than In the dfs process, a minimum value of a path is found, and the minimum value is subtracted from all edges on the path, and it is repeated until there is no pipe to flow. We call a path of energy flow an augmenting path.
It will flow like this. This picture is also the residual picture, which is the picture that is currently flowing.
This line of thinking is clearly correct for the above example.
But if a thin tube is inserted horizontally between the water pipes, this practice may become a fly.
As long as you click the big-eye observation skill, you can find that the maximum flow in the above picture should be 2, but your invincible algorithm runs out of 1. What is going on? It's because you dfs the wrong order. According to common sense in life, you can't blow the water back into the faucet and let the water flow back, then you may need a brand new operation to create a reverse edge to achieve the purpose of blowing the water back, no Wrong, it really blows back.
Or this diagram of connecting the toilet sewer pipe to the kitchen drinking water pipe (no. But we created the reverse edge
Each time a route is flown, how much the forward-side flow is reduced, the corresponding reverse-side flow is added.
Then take the flow reverse as a reasonable decision to continue with dfs.
The current answer is 2.
This approach is correct.
Because after (1, 2, 3, 4) flowed, (1, 3) flowed again, and found that (1, 2) flowed the road of (3, 4), so he shouted: "It's obvious that I should flow. Yes, why are you so skilled." Well, at first glance, it's not serious.
Then (1, 3) pushes the water flow back along (3, 2), restoring the edge (3, 2).
At this time (1, 3, 2) flows through (2, 4) again, and tells him: "You don't think you can flow the fuck?", and then the flow of (3, 4) gives (1, 3) , (1, 2) flow (2, 4) obediently.
Then the final result is (1, 3) flow (3, 4), (3, 2) flow back, (1, 2) flow (2, 4),
Let's just pretend that nothing happened, and continue to seek augmentation with dfs.
All in all, the reverse edge is equivalent to giving your program a chance to go back.
So how to implement the reverse edge? It is known that the count variable cnt used by the build edge function is continuous, and the number of the reverse edge is the number of the positive edge plus one. Let’s set the initial value of cnt to be 1 1 1 , then take the first set of positive and negative edges as an example, the number of positive edges is 2 2 2, the reverse side is 3 3 3, both can be XORed 1 1 1 get each other.
So far, I have summed up the idea, starting from the source, as long as the residual amount on the edge is not 0 0 0 , we flow through this edge, then recurse until we find the end point, and subtract the actual flow from the edge.
int dfs(int now,int rem)//rem is the residual amount, that is, the [water flow] from the source
{
if(now==n)return rem;
int tmp=rem;
for(int i=head[now];i;i=e[i].next)
{
int v=e[i].to;
if(e[i].w)
{
int k=min(e[i].w,tmp);//Take the smaller value between the maximum flow on the path and the edge residual
int dlt=dfs(v,k);//Solve for how much traffic can flow through this edge
e[i].w-=dlt;e[i^1].w+=dlt;//Optimization: Reverse Edge
tmp-=dlt;//Diverted flow reduced
if(!tmp)break;
}
}
return rem-tmp;//Returns how much traffic actually flowed
}
The basic idea is fine, let's use an extreme example to see the inefficiency of the algorithm so far:
For this graph, if your program takes the (1, 2, 3, 4) flow method, then the reverse edge (3, 2) becomes 1 1 1, and then if your program takes the flow method of (1, 3, 2, 4) again, and (2, 3) restores, the flow at this time is 2 2 2, so reciprocating, the program will be executed 1998 1998 After 1998 times, the answer was successfully obtained. But obviously we just need the stream 2 2 2 times to get the answer.
At this time, we need the idea of layered graphs, borrowing the idea of letting gravity make "water flow only to low places".
The core idea is to use bfs to process the graph once, process the depth of each point on the graph, and then dfs.
Then dfs can only recurse to a deeper place each time, just like water can only flow from high mountains to low-lying city centers, instead of repeating the flow on the "ring road" to waste resources.
That's probably how it's written, eh.
bool bfs()//seek augmentation road
{
memset(dis,0,sizeof(dis));
dis[1]=1;
queue<int>q;
q.push(1);//put in starting point
while(!q.empty())
{
int u=q.front();q.pop();
rad[u]=head[u];//restore current arc
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(!dis[v]&&e[i].w)//If this point has not been traversed, and flow is allowed (a necessary condition for augmenting path)
dis[v]=dis[u]+1,q.push(v);
}
}
return dis[n];//Can it flow to the end?
}
int dfs(int now,int rem)//rem is the residual amount, that is, the [water flow] from the source
{
if(now==n)return rem;
int tmp=rem;
for(int i=head[now];i;i=e[i].next)
{
int v=e[i].to;
if(dis[v]==dis[now]+1&&e[i].w)//Optimization: Hierarchical graph
{
int k=min(e[i].w,tmp);//Take the smaller of the maximum flow on the path and the edge capacity
int dlt=dfs(v,k);//Solve for how much traffic can flow through this edge
e[i].w-=dlt;e[i^1].w+=dlt;//Optimization: Reverse Edge
tmp-=dlt;//Diverted flow reduced
if(!tmp)break;
}
}
return rem-tmp;//Returns how much traffic actually flowed
}
int dicnic()
{
int ans=0;
while(bfs())ans+=dfs(1,1e9); //Set the starting residual to infinity
return ans;
}
Of course, the optimized dinic is still not good enough. We need a new optimization, the current arc optimization.
The name sounds awesome, but it's actually a way to remove redundancy.
For example, if you look at this picture, after you solve (1, 3, 4, ..., 9), it is actually possible that (4, 6), (4, 7) and so on have no possibility of augmentation. There is not a drop left, then when you (1, 2, 4) expand again, many paths do not need to be traversed at all, then we simply set up a rad array to record which edge was expanded last time. , the next time you start traversing directly from the edge of rad.
bool bfs()//seek augmentation road
{
memset(dis,0,sizeof(dis));
dis[1]=1;
queue<int>q;
q.push(1);
while(!q.empty())
{
int u=q.front();q.pop();
rad[u]=head[u];//restore current arc
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(!dis[v]&&e[i].w)//If this point has not been traversed, and flow is allowed (a necessary condition for augmenting path)
dis[v]=dis[u]+1,q.push(v);
}
}
return dis[n];//Can it flow to the end?
}
int dfs(int now,int rem)//rem is the residual amount, that is, the [water flow] from the source
{
if(now==n)return rem;
int tmp=rem;
for(int i=rad[now];i;i=e[i].next)//Optimization: Current Arc
{
int v=e[i].to;rad[now]=i;
if(dis[v]==dis[now]+1&&e[i].w)//Optimization: Hierarchical graph
{
int k=min(e[i].w,tmp);//Take the smaller of the maximum flow on the path and the edge capacity
int dlt=dfs(v,k);//Solve for how much traffic can flow through this edge
e[i].w-=dlt;e[i^1].w+=dlt;//Optimization: Reverse Edge
tmp-=dlt;//Diverted flow reduced
if(!tmp)break;
}
}
return rem-tmp;//Returns how much traffic actually flowed
}
int dicnic()
{
int ans=0;
while(bfs())ans+=dfs(1,1e9);
return ans;
}
The complete code, take P1343 as an example, put the standard range:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=205,maxm=2005;
int n,m,x,cnt=1;
int head[maxn],rad[maxn],dis[maxn];
struct node
{int next,to,w;}e[maxm*2];
void build(int u,int v,int w)
{e[++cnt].to=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;}
inline int read()
{
int x=0;char r=getchar();
while(r<'0'||r>'9')r=getchar();
while(r>='0'&&r<='9')
{x=x*10+r-'0';r=getchar();}
return x;
}
void init()
{
n=read();m=read();x=read();
for(int i=1,x,y,z;i<=m;i++)
{
x=read();y=read();z=read();
build(x,y,z);
build(y,x,0);//opposite side
}
}
bool bfs()//seek augmentation road
{
memset(dis,0,sizeof(dis));
dis[1]=1;
queue<int>q;
q.push(1);
while(!q.empty())
{
int u=q.front();q.pop();
rad[u]=head[u];//restore current arc
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(!dis[v]&&e[i].w)//If this point has not been traversed, and flow is allowed (a necessary condition for augmenting path)
dis[v]=dis[u]+1,q.push(v);
}
}
return dis[n];//Can it flow to the end?
}
int dfs(int now,int rem)//rem is the residual amount, that is, the [water flow] from the source
{
if(now==n)return rem;
int tmp=rem;
for(int i=rad[now];i;i=e[i].next)//Optimization: Current Arc
{
int v=e[i].to;rad[now]=i;
if(dis[v]==dis[now]+1&&e[i].w)//Optimization: Hierarchical graph
{
int k=min(e[i].w,tmp);//Take the smaller of the maximum flow on the path and the edge capacity
int dlt=dfs(v,k);//Solve for how much traffic can flow through this edge
e[i].w-=dlt;e[i^1].w+=dlt;//Optimization: Reverse Edge
tmp-=dlt;//Diverted flow reduced
if(!tmp)break;
}
}
return rem-tmp;//Returns how much traffic actually flowed
}
int dicnic()
{
int ans=0;
while(bfs())ans+=dfs(1,1e9);
return ans;
}
int main()
{
init();//read data
int a=dicnic();
if(a!=0)
{
if(x%a)printf("%d %d",a,(x-x%a)/a+1);
else printf("%d %d",a,x/a);
}
else printf("Orz Ni Jinan Saint Cow!");
return 0;
}