Detailed explanation of network flow (what information can the flow network diagram generally reflect)

大家好,又见面了,我是你们的朋友全栈君.

network-flows,网络流,The legendary province selected algorithm

To recommend a speak network flow your mindblog：

https://www.cnblogs.com/ZJUT-jiangnan/p/3632525.html

There are two kinds of network flow method,dinic和sap（isap） I was too weak,只会dinic

目的

首先,What is clear network flow

给定指定的一个有向图,其中有两个特殊的点源S(Sources)和汇T(Sinks),每条边有指定的容量(Capacity),求满足条件的从S到T的最大流(MaxFlow).

Here is a popular point to explain

Like to send your house Waterworks is the source

然后自来水厂和你家之间修了很多条水管子接在一起 水管子规格不一 有的容量大 有的容量小

然后Ask waterworks sluice 你家收到水的最大流量是多少

If the waterworks water supply The flow of your house that is0 Of course not the biggest traffic But you give water plant made100w美金 Water works hard in conduit water But the flow of your home would be so much the same 这时就达到了最大流

Ok, understand,Also is said to be

实现

Now know exactly what the,But how to ask？

Give a model as follows

首先来手算一下,很容易可以得出这个最大流是走（1,2,4）和（1,3,4）得到的2,即最大流为2

Then the program,We first introduce a called残量图的概念

顾名思义,The residual?,The meaning of is left,The remaining quantity,We put a maximum capacity on the side ofMAXVAnd the actual trafficFThe difference is called residual,即

残量= M A X V − F MAXV – F MAXV−F

Then we will residual as each edge has a weight,Build a graph is called a residual,若权值为0,Then the equivalent of a broken edge

此时,Suppose we set out from the source to onedfsTo collect,Then shows the route traffic can also add,Concrete increase quantity is the route traffic on the boundary determines the minimum,We take this road is called augmented road

就像上图,我们知道（1,2,3,4）This route is can increase in the flow,And the biggest can increase traffic is1,Reason we after his side's residual-1Got the figure

然后我们再dfs,Only to find that cannot reach collect,And so this time it returns the maximum flow at this time,1

But is not the case？？

这个时候我们发现,如果程序在dfs到2If can to4dfsIt wouldn't make a mistake！那么这个时候,If we give the figure marked every point on the depth,我们dfsWhen only allows high depth from low depth go,Wouldn't it be can significantly prevent mistakes？于是这个时候dinicAlgorithm ideas came out,Is withbfsThe depth and then constantlydfsUntil cannot reach collect

But just by mark depth can completely solve the problem？答案是不能的,Even if it can significantly reduce

That if we can make the programdfs到3When found the problem and regret notok了吗？

If you want to reach this level,We can write a learning algorithm of artificial intelligence,但是注意了,This is a race,Is to funny not to destroy human ha ha ha ha

So there is a the mosteasyThe method is to introduce the concept of a reverse side（How to introduce concept of so much）,That each side（u,v）都有一条反向边(v,u),And the two side equals the maximum capacity,The maximum flow equal the sum of the actual flow,即

M A X V ( u , v ) = M A X V ( v , u ) MAXV(u,v)=MAXV(v,u) MAXV(u,v)=MAXV(v,u)

F ( u , v ) = F ( v , u ) = M A X V ( v , u ) = M A X V ( u , v ) F(u,v)=F(v,u)=MAXV(v,u)=MAXV(u,v) F(u,v)=F(v,u)=MAXV(v,u)=MAXV(u,v)

由于定义,When an edge flow+或-a时,The reverse side of the traffic flow-或+a

If we introduce the concept of reverse side after,There is such a figure

然后根据dfs,We found the way to augmented（1,2,3,4）,Then figure it become like this

然后我们继续dfs,The edge of the reverse side as to godfs,And then got the augmented road（1,3,2,4）

Then the figure is so

最大流为2

仔细观察可以发现,Above and actually we directlydfs（1,2,4）和（1,3,4）得到的结果一样！！This is the right！！

But why can correct？The program and not let out a cry“啊,Shouldn't be that way！”

In fact the secret in the first2个dfs

When the program will edge（3,2）The flow with a,（2,3）Traffic reduction,It is equivalent to the edge（2,3）Traffic to return to the（Do not believe you see return after（2,3）和原图的（2,3）是不是一样的）,Then also belonged to the path（1,2,3,4）的流量“交付”给了（1,3）,So there will be a two way（1,2,4）和（1,3,4）

This is the secret

So the algorithm framework on the surface：

The depth first, then withdfsFind an augmented way thenbfsThe depth indfs然后bfs,dfs,bfs,dfs,bfs,dfs,bfs,dfs…直到bfsWhen find fault,That had a maximum flow at this time

Give a code below,Some details still need to see

题目来源：luoguP1343

//dinic
#include<bits/stdc++.h>
using namespace std;
#define INF INT_MAX
const int maxn=200+5;
const int maxm=2000+5;
int n,m,x,cnt=0;
int head[maxn];
int dis[maxn];
struct node
{ 
   
    int e;
    int v;
    int nxt;
}edge[maxm<<1];
//**********************************function
inline int read(){ 
   
   int ans=0;char r=getchar();
   while(r<'0'||r>'9')r=getchar();
   while(r>='0'&&r<='9'){ 
   ans=ans*10+r-'0';r=getchar();}
   return ans;
}
inline void addl(int u,int v,int w)
{ 
   
    edge[cnt].e=v;
    edge[cnt].v=w;
    edge[cnt].nxt=head[u];
    head[u]=cnt++;
}
void datasetting()
{ 
   
    memset(head,-1,sizeof(head));
    n=read();m=read();x=read();
    int a,b,c;
    for(int i=0;i<m;i++)
    { 
   
        a=read();b=read();c=read();
        addl(a,b,c);addl(b,a,0);//Plus side and reverse side
    }
}
bool bfs()//bfsLooking for depth
{ 
   
    memset(dis,-1,sizeof(dis));//注意！Don't forget this
    dis[1]=0;//Depth of the starting point for the0,From the source to sinkbfs
    queue<int>q;
    q.push(1);
    while(!q.empty())
    { 
   
        int r=q.front();q.pop();
        for(int i=head[r];i!=-1;i=edge[i].nxt)
        { 
   
            int j=edge[i].e;
            if(dis[j]==-1&&edge[i].v)//If the point has not beenbfsAnd the edge of the traffic is not as0
            { 
   
                dis[j]=dis[r]+1;
                q.push(j);
            }
        }
    }
    return dis[n]!=-1;//If not to the end（起点）就返回false 
}
int dfs(int u,int flo)//dfsNode is ouAnd its subtrees in the residual asfloWhen the maximum increment 
{ 
   
    if(u==n)return flo;//If it is collect,直接返回flo
    int detla=flo;//用一个变量来保存flo,To update the remaining residual
    for(int i=head[u];i!=-1;i=edge[i].nxt)
    { 
   
        int v=edge[i].e;
        if(dis[v]==(dis[u]+1)&&(edge[i].v)>0)//If meet the depth conditions and side can go
        { 
   
            int d=dfs(v,min(detla,edge[i].v));//向下递归
            //求vAnd its subsequent nodes in the residual asmin(detla,edge[i].v)时的最大流量
            edge[i].v-=d;edge[i ^ 1].v+=d;//边的处理
            //注意,编号为iIn the reverse side of the edge of Numbers fori^1,This is according to the save sidecnt决定的
            detla-=d;//The remaining remnants of this node quantity update
            if(detla==0)break;//If this node has no residual can be consumed,就返回
        }
    }
    return flo-detla;//Return to this point have been allowed to flow through the flow
}
int dini()//求最大流量
{ 
   
    int ans=0;
    while(bfs())
    { 
   
        ans+=dfs(1,INF);//用INFBecause we don't know at this time of the residual quantity how much（Actually this question is worth thinking）
    }
    return ans;
}
//**********************************main
int main()
{ 
   
   freopen("datain.txt","r",stdin);
   datasetting();
   int a=dini();
   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;
}
/********************************************************************
    ID:Andrew_82
    LANG:C++
    PROG:network-flows
********************************************************************/

复制

优化

当然,为了提高效率,We can introduce a place calledcur数组的东西

Don't know is which guy want to come out of exotic curiosity-a solution looking

原理是什么呢？Is when we are on a nodeu（假设有6儿子）When augmented,把他的儿子1,2,3,4Used up all of the available flow,那么在下一次dfsThe module go tou时,If we can directly from the son5You can begin augmented dramatically reduce the time of the additional overhead

具体怎么实现？

我们可以在dfsDo a little change inside,即先定义一个cur数组,在dfsThe adjacency list beforehead数组拷贝到cur里面,然后在遍历u的时候同时把curThe edge of the inside of the subscript aft,In order to reach the purpose of will run out of side out

代码（加cur优化）

//P1343
#include<bits/stdc++.h>
using namespace std;
#define INF INT_MAX
const int maxn=200+5;
const int maxm=2000+5;
int n,m,x,cnt=0;
int head[maxn];
int dis[maxn];
struct node
{ 
   
    int e;
    int v;
    int nxt;
}edge[maxm<<1];
int cur[maxn];
//**********************************function
inline int read(){ 
   
   int ans=0;char r=getchar();
   while(r<'0'||r>'9')r=getchar();
   while(r>='0'&&r<='9'){ 
   ans=ans*10+r-'0';r=getchar();}
   return ans;
}
inline void addl(int u,int v,int w)
{ 
   
    edge[cnt].e=v;
    edge[cnt].v=w;
    edge[cnt].nxt=head[u];
    head[u]=cnt++;
}
void datasetting()
{ 
   
    memset(head,-1,sizeof(head));
    n=read();m=read();x=read();
    int a,b,c;
    for(int i=0;i<m;i++)
    { 
   
        a=read();b=read();c=read();
        addl(a,b,c);addl(b,a,0);
    }
}
bool bfs()
{ 
   
    memset(dis,-1,sizeof(dis));
    dis[1]=0;
    queue<int>q;
    q.push(1);
    while(!q.empty())
    { 
   
        int r=q.front();q.pop();
        for(int i=head[r];i!=-1;i=edge[i].nxt)
        { 
   
            int j=edge[i].e;
            if(dis[j]==-1&&edge[i].v)
            { 
   
                dis[j]=dis[r]+1;
                q.push(j);
            }
        }
    }
    return dis[n]!=-1;//If not to the end（起点）就返回false 
}
int dfs(int u,int flo)//dfsNode is ouIn the residual asfloWhen the maximum increment 
{ 
   
    if(u==n)return flo;
    int detla=flo;
    for(int i=cur[u];i!=-1;i=edge[i].nxt)
    { 
   
        cur[u]=edge[i].nxt;
        int v=edge[i].e;
        if(dis[v]==(dis[u]+1)&&(edge[i].v)>0)
        { 
   
            int d=dfs(v,min(detla,edge[i].v));
            edge[i].v-=d;edge[i ^ 1].v+=d;
            detla-=d;
            if(detla==0)break;
        }
    }
    return flo-detla;//Return to this point have been allowed to flow through the flow
}
int dini()
{ 
   
    int ans=0;
    while(bfs())
    { 
   
        for(int i=1;i<=n;i++)cur[i]=head[i];
        ans+=dfs(1,INF);
    }
    return ans;
}
//**********************************main
int main()
{ 
   
   
   datasetting();
   int a=dini();
   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;
}
/********************************************************************
    ID:Andrew_82
    LANG:C++
    PROG:network-flows
********************************************************************/

复制

衍生问题

鲁迅说：The code only popularity of network flow group difficulty,Modeling is the most important thing

最小费用最大流问题

问题

给出一个网络图,以及其源点和汇点,每条边已知其最大流量和单位流量费用,求出其网络最大流和在最大流情况下的最小费用.

实现

As is required in the case of maximum flow down to find the minimum cost,Easy to think of a way is先求出最大流,Then with a deep search to find the minimum

好像是可以的,But as a lazy and stupid konjac,I didn't go to try this way,And estimate the nakeddfsThere will be a big explosion possibility of stack

那么他既然要求最小花费,我们不妨把这个最小花费看成边的权值,构建一个图用最短路算法来找到源点到各个点的最短距离

找到这个数据之后,我们就可以沿着最短路来进行增广,即在最短路中求到一条可行路然后修改其残量,我们可以保证其为最大流中的一部分的最小花费

不断的进行增广直到我们找到了全部值,然后得解,这就是将dinic和spfa结合起来的求解最小费用最大流问题的方法

具体代码如下 (luoguP3381)

#include<bits/stdc++.h>
using namespace std;
const int INF=INT_MAX;
const int maxn=5000+5,maxm=50000+5;
int n,m,s,t,cnt=0;
int head[maxn];
int dis[maxn];
int result=0;
int minfee=0;
bool vis[maxn];
struct node
{ 
   
	int e;
	int nxt;
	int w;//Refers to the weight 
	int f;//Refers to the flow 
}edge[maxm<<1];
//**********************************function
inline void addl(int u,int v,int flow,int cost)
{ 
   
	edge[cnt].e=v;
	edge[cnt].w=cost;
	edge[cnt].f=flow;
	edge[cnt].nxt=head[u];
	head[u]=cnt++;
}
inline int read()
{ 
   
   int ans=0;
   char r=getchar();
   while(r<'0'||r>'9')r=getchar();
   while(r>='0'&&r<='9')
   { 
   
      ans=ans*10+r-'0';
      r=getchar();
   }
   return ans;
}
void datasetting()
{ 
   
	memset(head,-1,sizeof(head));
	n=read();m=read();s=read();t=read();
	int ui,vi,wi,fi;
	for(int i=0;i<m;i++)
	{ 
   
		ui=read();vi=read();wi=read();fi=read();//fiIs a unit flow cost,wi是最大流量 
		addl(ui,vi,wi,fi);//Toward the edge of the weight offi,流量为wi
		addl(vi,ui,0,-fi);//The reverse side of a weight of-fi,流量为0 
	}
}
bool spfa(int u,int v)
{ 
   
	for(int i=0;i<maxn;i++)dis[i]=INF;//spfa基本操作
	memset(vis,false,sizeof(vis));//spfaQueue up weight optimization
	dis[u]=0;
	deque<int>d;//spfa的slf优化
	d.push_back(u);
	vis[u]=true;
	while(!d.empty())
	{ 
   
		int ui=d.front();d.pop_front();vis[ui]=false;//uiIs the starting point of the current loose edge
		for(int i=head[ui];i!=-1;i=edge[i].nxt)
		{ 
   
			int vi=edge[i].e;int w=edge[i].w;int f=edge[i].f;//viIs the end of the current loose edge 
			if(f&&dis[vi]>dis[ui]+w)//If the current residual quantity and is the shortest way while just to relax
			{ 
   
				dis[vi]=dis[ui]+w;
				if(!vis[vi])
				{ 
   
					if(!d.empty()&&dis[vi]<dis[d.front()])d.push_front(vi);
					else d.push_back(vi);
				}
			}
		}
	}
	return dis[t]!=INF;
}
int dfs(int u,int flow)
{ 
   
	if(u==t)return flow;
	int detla=flow;
	vis[u]=true;
	for(int i=head[u];i!=-1;i=edge[i].nxt)
	{ 
   
		int v=edge[i].e;int w=edge[i].w;int f=edge[i].f;
		if(f&&!vis[v]&&dis[v]==dis[u]+w)//注意,A point can only access a,这个可以用vis来维护（vis在spfa模块和dfsModules are used in,注意初始化）
		{ 
   
			int d=dfs(v,min(f,detla));
			detla-=d;
			edge[i].f-=d;edge[i^1].f+=d;
			minfee+=d*w;//Update the cost（单价x流量）
			if(detla==0)break;
		}
	}
	vis[u]=false;
	return flow-detla;
}
void dinic()
{ 
   
	result=0;
	while(spfa(s,t))
	{ 
   
		memset(vis,false,sizeof(vis));
		result+=dfs(s,INF);
	}
	printf("%d %d",result,minfee);
}
//**********************************main
int main()
{ 
   
   freopen("datain.txt","r",stdin);
   datasetting();
   dinic();
   return 0;
}
/********************************************************************
   ID:Andrew_82
   LANG:C++
   PROG:network flow
********************************************************************/

复制

attention：

1.fi是单价,Rather than the edge right,The actual edge right=流量 × \times ×单价

2.For each road can be improved,The flow is the same,So at the time of renewal fees can directly with fi × \times ×流量 了

More advanced modeling referenceluogu-网络流24题

发布者：全栈程序员栈长,转载请注明出处：https://javaforall.cn/125494.html原文链接：https://javaforall.cn