网络流算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了网络流算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4599字，纯文字阅读大概需要7分钟。
内容图文
原文博客：https://blog.csdn.net/stevensonson/article/details/79177530
网络流图是一张只有一个源点和汇点的有向图，而最大流就是求源点到汇点间的最大水流量，下图的问题就是一个最基本，经典的最大流问题
二.流量，容量和可行流
对于弧(u,v)来说，流量就是其上流过的水量(我们通常用f(u,v)表示)，而容量就是其上可流过的最大水量(我们通常用c(u,v)表示)，只要满足f(u,v)<=c(u,v)，我们就称流量f(u,v)是可行流(对于最大流问题而言，所有管道上的流量必须都是可行流)。
三.增广路
如果一条路上的所有边均满足:正向边: f(u,v)< c(u,v) ——– 反向边：f(u,v)> 0则我们称这条路径为一条增广路径，简称增广路。
好了，弄懂了一些定义，接下来就可以介绍著名的Ford-Fulkerson算法了。
如图所示，如果我们每次都找出一条增广路，只要这条增广路经过汇点，那说明此时水流还可以增加，增加的量为d(d=min(d,c(u,v)-f(u,v))或d=min(d,f(u,v)))。
我们可以这样理解：对于每一条正向边，他能添加的最大水流为c(u,v)-f(u,v)。而对于反向边来说，当正向边上的水流增多时，反向边自身的反向水流会减少，而其能减少的最多水量为f(u,v)。由于要保证添加水流之后，所有的f(u,v)都是可行流，所以我们取最小值。
增加之后，我们要更新流量，每条正向边+d,每条反向边-d即可。
既然这样，我们的思路就是：
1.找出一条增广路径 ——2.修改其上点的值——3.继续重复1，直至找不出增广路。则此时源点的汇出量即为所求的最大流。
我这里就不贴这个算法的代码了，想看的可以去原文上面看。在这里我贴一下DINIC算法代码模板：
DINIC算法
Dinic算法是网络流最大流的优化算法之一，每一步对原图进行分层，然后用DFS求增广路。时间复杂度是O(n^2*m)，Dinic算法最多被分为n个阶段，每个阶段包括建层次网络和寻找增广路两部分。
Dinic算法的思想是分阶段地在层次网络中增广。它与最短增广路算法不同之处是：最短增广路每个阶段执行完一次BFS增广后，要重新启动BFS从源点st开始寻找另一条增广路;而在Dinic算法中，只需一次BFS过程就可以实现多次增广。
简单来说，分为下面几步：
1.在剩余网络中查找是否存在从S到T的路径，同时建分层图。
分层图的层数其实就是S到i这个点需要几步。
2.沿着分层图多路增广。
增广时一定要满足dis[j]=dis[i]+1。
3.直到没有S到T的路径是结束算法。
下面代码的题目解析可以到这里看https://www.cnblogs.com/kongbursi-2292702937/p/11782283.html
代码：
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 #include<queue>
6 using namespace std;
7 const int maxn=10000;
8 const int INF=0x3f3f3f3f;
9 int head[maxn],cnt,st,en,dis[maxn],cur[maxn];
10 struct edge
11 {
12 int v,next,c,flow;
13 }e[maxn];
14 void add_edge(int x,int y,int z)
15 {
16 e[cnt].v=y;
17 e[cnt].c=z;
18 e[cnt].flow=0;
19 e[cnt].next=head[x];
20 head[x]=cnt++;
21 }
22 bool bfs()
23 {
24 memset(dis,0,sizeof(dis));
25 dis[st]=1;
26 queue<int>r;
27 r.push(st);
28 while(!r.empty())
29 {
30 int x=r.front();
31 r.pop();
32 for(int i=head[x];i!=-1;i=e[i].next)
33 {
34 int v=e[i].v;
35 if(!dis[v] && e[i].c>e[i].flow)
36 {
37 dis[v]=dis[x]+1;
38 r.push(v);
39 }
40 }
41 }
42 return dis[en];
43 }
44 int dinic(int s,int limit)
45 {
46 if(s==en || !limit) return limit;
47 int ans=0;
48 for(int &i=cur[s];i!=-1;i=e[i].next)
49 {
50 int v=e[i].v,feed;
51 if(dis[v]!=dis[s]+1) continue;
52 feed=dinic(v,min(limit,e[i].c-e[i].flow));
53 if(feed)
54 {
55 e[i].flow+=feed;
56 e[i^1].flow-=feed;
57 limit-=feed;
58 ans+=feed;
59 if(limit==0) break;
60 }
61 }
62 if(!ans) dis[s]=-1;
63 return ans;
64 }
65 int main()
66 {
67 memset(head,-1,sizeof(head));
68 //从这开始都是建图
69 int n,f,d;
70 scanf("%d%d%d",&n,&f,&d);
71 st=0;
72 en=2*n+f+d+1;
73 for(int i=1;i<=f;++i)
74 {
75 add_edge(st,2*n+i,1);
76 add_edge(2*n+i,st,0);
77 }
78 for(int i=1;i<=d;++i)
79 {
80 add_edge(2*n+f+i,en,1);
81 add_edge(en,2*n+f+i,0);
82 }
83 for(int i=1;i<=n;++i)
84 {
85 add_edge(i,n+i,1);
86 add_edge(n+i,i,0);
87 int sum1,sum2;
88 scanf("%d%d",&sum1,&sum2);
89 int x;
90 for(int j=0;j<sum1;++j)
91 {
92 scanf("%d",&x);
93 add_edge(x+2*n,i,1);
94 add_edge(i,x+2*n,0);
95 }
96 for(int j=0;j<sum2;++j)
97 {
98 scanf("%d",&x);
99 add_edge(n+i,x+f+2*n,1);
100 add_edge(x+f+2*n,n+i,0);
101 }
102 }
103 //到这建图结束
104
105 int ans=0;
106 while(bfs())
107 {
108 for(int i=0;i<=en;i++)
109 cur[i]=head[i];
110 ans+=dinic(st,INF);
111 }
112 printf("%d\n",ans);
113 return 0;
114 }
内容总结
以上是互联网集市为您收集整理的网络流算法全部内容，希望文章能够帮你解决网络流算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。