算法中的网络流是什么意思？请简单介绍一下啊？

网络流的最大流和最小流是什么算法~

首先是网络流中的一些定义：
V表示整个图中的所有结点的集合.
E表示整个图中所有边的集合.
G = (V,E) ,表示整个图.
s表示网络的源点,t表示网络的汇点.
对于每条边(u,v),有一个容量c(u,v) (c(u,v)>=0)，如果c(u,v)=0，则表示(u,v)不存在在网络中。相反，如果原网络中不存在边(u,v)，则令c(u,v)=0.
对于每条边(u,v),有一个流量f(u,v).

一个简单的例子.网络可以被想象成一些输水的管道.括号内右边的数字表示管道的容量c,左边的数字表示这条管道的当前流量f.


网络流的三个性质：
1、容量限制: f[u,v]<=c[u,v]
2、反对称性：f[u,v] = - f[v,u]
3、流量平衡: 对于不是源点也不是汇点的任意结点,流入该结点的流量和等于流出该结点的流量和。
只要满足这三个性质,就是一个合法的网络流.
最大流问题，就是求在满足网络流性质的情况下，源点 s 到汇点 t 的最大流量。


求一个网络流的最大流有很多算法 这里首先介绍 增广路算法（EK）
学习算法之前首先看了解这个算法中涉及到的几个图中的定义：

**残量网络
为了更方便算法的实现，一般根据原网络定义一个残量网络。其中r(u,v)为残量网络的容量。
r(u,v) = c(u,v) – f(u,v)
通俗地讲：就是对于某一条边（也称弧），还能再有多少流量经过。
Gf 残量网络,Ef 表示残量网络的边集.

这是上面图的一个残量网络。残量网络（如果网络中一条边的容量为0,则认为这条边不在残量网络中。
r(s,v1)=0,所以就不画出来了。另外举个例子：r(v1,s) = c(v1,s) – f(v1,s) = 0 – (-f(s,v1)) = f(s,v1) = 4.
其中像(v1,s)这样的边称为后向弧,它表示从v1到s还可以增加4单位的流量。
但是从v1到s不是和原网络中的弧的方向相反吗？显然“从v1到s还可以增加4单位流量”这条信息毫无意义。那么，有必要建立这些后向弧吗？
显然，第1个图中的画出来的不是一个最大流。
但是，如果我们把s -> v2 -> v1 -> t这条路径经过的弧的流量都增加2,就得到了该网络的最大流。
注意到这条路径经过了一条后向弧:(v2,v1)。
如果不设立后向弧，算法就不能发现这条路径。
**从本质上说，后向弧为算法纠正自己所犯的错误提供了可能性，它允许算法取消先前的错误的行为（让2单位的流从v1流到v2)

注意,后向弧只是概念上的,在程序中后向弧与前向弧并无区别.

**增广路
增广路定义：在残量网络中的一条从s通往t的路径，其中任意一条弧(u,v)，都有r[u,v]>0。

如图绿色的即为一条增广路。

看了这么多概念相信大家对增广路算法已经有大概的思路了吧。

**增广路算法
增广路算法：每次用BFS找一条最短的增广路径，然后沿着这条路径修改流量值（实际修改的是残量网络的边权）。当没有增广路时，算法停止，此时的流就是最大流。


**增广路算法的效率
设n = |V|, m = |E|
每次增广都是一次BFS,效率为O(m),而在最坏的情况下需要（n-2增广。（即除源点和汇点外其他点都没有连通，所有点都只和s与t连通）
所以,总共的时间复杂度为O(m*n)，所以在稀疏图中效率还是比较高的。

hdoj 1532是一道可以作为模板题目练手。
模板代码：

[cpp] view plain copy print?
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int N = 1100;
const int INF = 0x3f3f3f3f;

struct Node
{
int to;//终点
int cap; //容量
int rev; //反向边
};

vector v[N];
bool used[N];

void add_Node(int from,int to,int cap) //重边情况不影响
{
v[from].push_back((Node){to,cap,v[to].size()});
v[to].push_back((Node){from,0,v[from].size()-1});
}

int dfs(int s,int t,int f)
{
if(s==t)
return f;
used[s]=true;
for(int i=0;i<v[s].size();i++)
{
Node &tmp = v[s][i]; //注意
if(used[tmp.to]==false && tmp.cap>0)
{
int d=dfs(tmp.to,t,min(f,tmp.cap));
if(d>0)
{
tmp.cap-=d;
v[tmp.to][tmp.rev].cap+=d;
return d;
}
}
}
return 0;
}

int max_flow(int s,int t)
{
int flow=0;
for(;;){
memset(used,false,sizeof(used));
int f=dfs(s,t,INF);
if(f==0)
return flow;
flow+=f;
}
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
memset(v,0,sizeof(v));
for(int i=0;i<n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add_Node(x,y,z);
}
printf("%d
",max_flow(1,m));
}
}

求网络流有很多算法，这几天学习了两种，记录一下EK算法。
首先是网络流中的一些定义：
V表示整个图中的所有结点的集合.
E表示整个图中所有边的集合.
G = (V,E) ,表示整个图.
s表示网络的源点,t表示网络的汇点.
对于每条边(u,v),有一个容量c(u,v) (c(u,v)>=0)，如果c(u,v)=0，则表示(u,v)不存在在网络中。相反，如果原网络中不存在边(u,v)，则令c(u,v)=0.
对于每条边(u,v),有一个流量f(u,v).

一个简单的例子.网络可以被想象成一些输水的管道.括号内右边的数字表示管道的容量c,左边的数字表示这条管道的当前流量f.


网络流的三个性质：
1、容量限制: f[u,v]<=c[u,v]
2、反对称性：f[u,v] = - f[v,u]
3、流量平衡: 对于不是源点也不是汇点的任意结点,流入该结点的流量和等于流出该结点的流量和。
只要满足这三个性质,就是一个合法的网络流.
最大流问题，就是求在满足网络流性质的情况下，源点 s 到汇点 t 的最大流量。


求一个网络流的最大流有很多算法 这里首先介绍 增广路算法（EK）
学习算法之前首先看了解这个算法中涉及到的几个图中的定义：

**残量网络
为了更方便算法的实现，一般根据原网络定义一个残量网络。其中r(u,v)为残量网络的容量。
r(u,v) = c(u,v) – f(u,v)
通俗地讲：就是对于某一条边（也称弧），还能再有多少流量经过。
Gf 残量网络,Ef 表示残量网络的边集.

这是上面图的一个残量网络。残量网络（如果网络中一条边的容量为0,则认为这条边不在残量网络中。
r(s,v1)=0,所以就不画出来了。另外举个例子：r(v1,s) = c(v1,s) – f(v1,s) = 0 – (-f(s,v1)) = f(s,v1) = 4.
其中像(v1,s)这样的边称为后向弧,它表示从v1到s还可以增加4单位的流量。
但是从v1到s不是和原网络中的弧的方向相反吗？显然“从v1到s还可以增加4单位流量”这条信息毫无意义。那么，有必要建立这些后向弧吗？
显然，第1个图中的画出来的不是一个最大流。
但是，如果我们把s -> v2 -> v1 -> t这条路径经过的弧的流量都增加2,就得到了该网络的最大流。
注意到这条路径经过了一条后向弧:(v2,v1)。
如果不设立后向弧，算法就不能发现这条路径。
**从本质上说，后向弧为算法纠正自己所犯的错误提供了可能性，它允许算法取消先前的错误的行为（让2单位的流从v1流到v2)

注意,后向弧只是概念上的,在程序中后向弧与前向弧并无区别.

**增广路
增广路定义：在残量网络中的一条从s通往t的路径，其中任意一条弧(u,v)，都有r[u,v]>0。

如图绿色的即为一条增广路。

看了这么多概念相信大家对增广路算法已经有大概的思路了吧。

**增广路算法
增广路算法：每次用BFS找一条最短的增广路径，然后沿着这条路径修改流量值（实际修改的是残量网络的边权）。当没有增广路时，算法停止，此时的流就是最大流。


**增广路算法的效率
设n = |V|, m = |E|
每次增广都是一次BFS,效率为O(m),而在最坏的情况下需要（n-2增广。（即除源点和汇点外其他点都没有连通，所有点都只和s与t连通）
所以,总共的时间复杂度为O(m*n)，所以在稀疏图中效率还是比较高的。

现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。如下图：
　　每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？
　　这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。
　　若有向图G=(V,E)满足下列条件：
　　1、 有且仅有一个顶点S，它的入度为零，即d-(S) = 0，这个顶点S便称为源点，或称为发点。
　　2、 有且仅有一个顶点T，它的出度为零，即d+(T) = 0，这个顶点T便称为汇点，或称为收点。
　　3、 每一条弧都有非负数，叫做该边的容量。边(vi, vj)的容量用cij表示。
　　则称之为网络流图，记为G = (V, E, C)

---

金阊区18894939288： 算法中的网络流是什么意思?请简单介绍一下啊? - ？
从高依姆： 现在想将一些物资从S运抵T,必须经过一些中转站.连接中转站的是公路,每条公路都有最大运载量.如下图: 每条弧代表一条公路,弧上的数表示该公路的最大运载量.最多能将多少货物从S运抵T? 这是一个典型的网络流模型.为了解答...

金阊区18894939288： 帮我解释下网络流 - ？
从高依姆： 必须知识:最短路径问题 1.Dijkstra 适用于满足所有权系数大于等于0(lij≥0)的网络最短路问题,能求出起点v1到所有其他点vj的最短距离; 朴素的Dijkstra算法复杂度为O(N^2),堆实现的Dijkstra复杂度为O(NlogN). 2.bellman-ford 适用于有负权系数...

金阊区18894939288： 网络流算法和并查集算法 - ？
从高依姆： ========================== 网络流(network flows) 1. 网络流先要构图 通常是一道题目最难的地方.(有的时候需要增加一个源点和一个汇点) 2. 然后就是不断找有没有可改进路 如果有则改进. 3. 当找到一条改进路时 需要找这条...

金阊区18894939288： C++网络流 残量网络是什么意思 传递闭包是什么意思,怎么求 - ？
从高依姆： 求网络流有很多算法,这几天学习了两种,记录一下EK算法.首先是网络流中的一些定义:V表示整个图中的所有结点的集合.E表示整个图中所有边的集合.G = (V,E) ,表示整个图.s表示网络的源点,t表示网络的汇点.对于每条边(u,v),有...

金阊区18894939288： 一条算法题,好像是关于网络流算法的大意是有一个m*n的矩阵,每个格子中都有一个高度为Hij的柱子,每次可以将每行或每列降低1,如果一个柱子高度为... - ？
从高依姆：[答案] 确实是网络流.不过不知道该怎么想. 需要保留每个点被减小的高度,0被降低后变成-1,被减少的高度应该为1 剩下的就不知道了

金阊区18894939288： 数学建模网络流算法重要吗?你们都用什么算法呢? - ？
从高依姆： 网络流很重要,它是一个基础算法.很多问题在经过一定的转化后能够变成这个问题.网络流我就用dinic

金阊区18894939288： 网络流的资料 - ？
从高依姆： 编辑本段定义 图论中的一种理论与方法,研究网络上的一类最优化问题 .1955年 ,T.E. 哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题.1956年,L.R. 福特和 D.R. 富尔克森等人给出了解决这类问题的...

金阊区18894939288： 请问C++中的输入流,输出流,这里的流是什么意思? - ？
从高依姆： 可以把流看作是一种数据的载体,通过它可以实现数据交换和传输. 就像水流是一串水组成的计算机中的数据流就是由一串数据组成的东西你越往后学,这个概念就会越清晰

金阊区18894939288： 网络流量是什么意思? - ？
从高依姆： 就是现在的智能手机都是对过 联通、电信或移动三大运营商的GPRS通信技术也上网的!会发生上传或下载数据.这个数据是流量 他们 也按这个数据来收流量费的.这还不明白 就是我们电脑用网线上网一样也会发生上传下载的数据吖.

金阊区18894939288： 网络流是NP完全问题吗,感觉很像,求解 - ？
从高依姆： 是.