http://yuanhuixie.blogcn.com/
流网络G=(V,E)是一个有向图,每一条边都有一非负容量 c(u,v)>=0.流网络中有两个特殊的点:源点 s 和汇点 t 。
最大流问题中,给出一个具有源点和汇点的流网络,希望找出从源点到汇点的最大值流。
解决最大流问题的 Ford-Fulkerson 方法依赖于三种重要的思想:残留网络、增广路径和割。
Ford-Fulkerson是一种迭代的方法,通过更新有边相连的每对顶点 u,v之间的网络流 f[u,v],来计算出图 G=(V,E)中的最大流。
class Link
{
public int key;
public int c;
public Link next;
public int Key
{
get
{ return key; }
set
{ key = value; }
}
public int C
{
get
{ return c; }
set
{ c = value; }
}
public Link Next
{
get
{ return next; }
set
{ next = value; }
}
public Link()
{
key = 0;
c = 0;
next = null;
}
public int Min() //返回残余容量
{
Link R=this.Next;
int min = this.C;
while (R != null)
{
if (min > R.C)
min = R.C;
R = R.Next;
}
return min;
}
}
public int[,] Ford_Fulkerson(int[,] G, int s, int t)
{
int c = 0;
Link P = new Link(); //P用于表示图 G 的一条增广路径。
int[,] f = new int[G.Length, G.Length];
for(int i=0;i<G.Length;i++)
for (int j = 0; j < G.Length; j++)
{
if (G[i, j] != 0) //如果(u,v)是图G的边,把那条边的流值初始化为0
{
f[i, j] = 0;
f[j, i] = 0;
}
}
while ((P = ExistPath(G))!=null) //这里判断图 G中是否有残余流网络,此函数可以用广度优先搜索,但是我还是没写好
{
c = P.Min(); //取出增广路径的残余容量 c
while(P.Next!=null)
{
f[P.Key, P.Next.Key] += c;
f[P.Next.Key, P.Key] = 0 - f[P.Key, P.Next.Key];
P = P.Next;
}
}
return f;
}
昨天写了最大流里面的 Ford-Fulkerson 算法,但是里面有个寻找函数 ExistPath(int[,] G, int s, int t, int[,] f) 我没写出来,今天写好了,现在再发一次:
public int[,] Ford_Fulkerson(int[,] G, int s, int t)
{
int c = 0;
Link P = new Link(); //P用于表示图 G 的一条增广路径。
int[,] f = new int[G.Length, G.Length];
for (int i = 0; i < G.Length; i++)
for (int j = 0; j < G.Length; j++)
{
if (G[i, j] != 0) //如果(u,v)是图G的边,把那条边的流值初始化为0
{
f[i, j] = 0;
f[j, i] = 0;
}
}
while ((P = ExistPath(G, s, t, f)) != null) //这里判断图 G中是否有残余流网络,返回增广路径
{
c = P.Min(); //取出增广路径的残余容量 c
while (P.Next != null)
{
f[P.Key, P.Next.Key] += c;
f[P.Next.Key, P.Key] = 0 - f[P.Key, P.Next.Key];
P = P.Next;
}
}
return f;
}
public Link ExistPath(int[,] G, int s, int t, int[,] f)
{
int j = s, k = 0, Next = 0;
int[] Pass = new int[G.Length];
for (int i = 0; i < G.Length; i++)
Pass[i] = -1;
Pass[k] = s; //用 Pass[] 记下遍历过程中经过的节点的顺序
Link L2 = new Link();
Link L = L2;
for (int i = 0; i < G.Length; i++)
{
if ((Next = NextNode(G, Pass, j)) != -1)
Pass[k++] = Next;
j = Next;
if (Next == t) //当到达汇点时就停止
break;
}
for (int i = 0; i < G.Length; i++)
{
L2.Key = Pass[i];
L2 = L2.Next;
if (Pass[i] == t) //当搜索过程中有到达汇点的就表示存在有增广路径
{
L2.Key = Pass[i];
return L;
}
}
return null;
}
public int NextNode(int[,] G, int[,] Pass, int j)
{
for (int i = 0; i < G.Length; i++)
{
if (Pass[i] == -1) //当节点没有被经过
{
if (G[j, i] != 0 && f[j, i] != G[j, i]) //当边(j,i)存在 且有残余容量时
{
return i;
}
}
}
return -1;
}
分享到:
相关推荐
网络的最小费用最大流,弧旁的数字是容量(运费)。 一.Ford和Fulkerson迭加算法. 基本思路:把各条弧上单位流量的费用看成某种长度,用求解最短路问题的方法确定一条自V1至Vn的最短路;在将这条最短路作为可扩充路...
对根据数值模拟结果研制的喷头及配套钻孔扩孔装备进行实验室试验和现场应用检验,结果表明,三维旋转水射流扩孔直径可达2.3倍、百米钻孔瓦斯抽采纯量最大可达常规钻孔1.79倍、59 d抽采率提高了79.3%,在低透煤层增透...
最大流 转换流。 比{mu,min}stache更快更简单。 安装 $ npm install maxstache-stream 用法 const maxstache = require ( 'maxstache-stream' ) const fs = require ( 'fs' ) fs . createReadStream ( './foobar....
对于有容量限制的多品种物资运输问题,不仅可以用传统的袁上作业法求解,还可以转化为最小费用最大流算法求解。事实证明,有容量限制的运输问题用最小费用最大流算法求解比表上作业法求解更方便。
该试验机可加强光电系统准确性,提高煤甑传动搅拌系统精度,具有煤质分析检测功能,通过与现有检测仪器和进口仪器检测结果对比,结果表明:特征温度和最大流动度重复性很好,精度分别控制在特征温度平均值不大于8℃、最大...
结果发现,扰流板的偏转导致最大升程增加了2.497%。 已发现,对于b = 10的情况,将扰流板偏转8°是最佳的。 较大的挠度都会降低升力增益,而25°的挠度会使最大升力比干净配置小2.786%。 在b = 15的情况下,δ= ...
电化学放电加工(Electrochemical Discharge Machining...计算结果表明,随着工具电极旋转速度增加,工具电极最大变形及工具电极最大应力增加;随着工具电极与微小孔偏心量的增加,工具电极最大变形及工具电极最大应力增加。
软件最大的功能就是用户通过该软件,可以将视频顺时针旋转、逆时针旋转、水平镜像、垂直镜像,快速的调整您的视频方向到正确的位置。软件支持一般编码格式的视频同时,也支持流行的手机设备的视频,支持大部分流行...
进行了实验研究,以研究在有和没有入口涡流条件下的90°双弯管下游的二维轴向速度场。 其主要目的是利用超声技术找到分离区域并观察进气涡流对... 另外,进气涡流条件主要影响切向速度的波动,其最大湍流强度为40%。
另外,下面讨论的最新动力学考虑的应用也刺激了这一预测,其中包括应用伯努利定律简化流向以及在跨流方向进行地转平衡。 这些引起了对较早解释的重新思考,从现在的反思来看,现在的解释似乎不太合适。
功能:在一个页面上展示数据库中的word文件流及word实体文件的内容样式! 独特优势: 1,改变传统页面展示word的模式(传统做法是先把数据库中的word文件流转换成word实体文件保存在服务器中,然后再把实体文件...
这款图文自由转软件最大的效用就是出错很少,减少了朋友还得改上面的错字,在我这款图文自由转中不会出现像这样的情况,完全放心使用,一点都不用担心。 这款软件的独特之处:除了具有一般同款软件的图片识别...
系统地分析了单脉冲和周期性脉冲流动在科氏力和离心力共同作用下的主流速度、二次流动变化情况,研究结果表明:旋转弯曲管道内脉冲流的流动特性主要由Dean数、曲率、周期内的最大科氏力与离心力之比、间歇频率参数和...
并利用FLUENT软件对立式集热板太阳能热气流电站系统进行数值模拟,在不同集热板高度、宽度和空气层厚度下的模拟结果表明:随着集热板高度、宽度和空气层厚度的增加,系统通风量和系统最大功率都是增大的,增大幅度越来越...
CS5466是一款高性能的Type-C到HDMI2.1协议转换器,通过Type-C/D DisplayPort链路接收视频和流,并转换为支持TMDS或FRL输出信令的HDM。HDMI输出端口可以作为TMDS或FRL发射机进行操作。FRL发射机符合HDMI2.1规范,支持...
必须预测性能和年发电量,以使风力涡轮机的经济利益最大化。 在数学上预测基于Darrieus型升力的涡轮机的性能具有挑战性,这是因为攻角不一致,叶片尾流相互作用和局部感应速度引起了复杂的流动物理学。 因此,可靠且...
重点2:这是本软件,优于市面上所有图像文字转换文本文字软件的,最大特征。 重点3:本软件支持快捷方式截图,能够像QQ使用快捷键一样,快键选择识别区域,这是网络上卖的其它软件所不具有的。 强大功能具体介绍: 1...
针对此类问题,建立了增益网络最大流模型,并通过增设虚弧将增益网络转换成循环网络,利用循环网络中汇点流量瞬间平衡的优点简化了模型。最后,结合实例进行分析,编写程序对实例进行了计算,计算结果验证了该模型的有效性...
当转速为400 r/min时,颗粒相主要分布在静止域转筒壁面附近,螺旋钻杆内部颗粒分布较少,在惯性力作用下颗粒贴附在螺旋钻杆壁面螺旋推流,颗粒体积分数较为均匀,推流效率较高。当转速为600 r/min时,静止域内部中间位置转...
流媒体实时传输技术是当前通信领域研究的热点之一,流媒体的最大特点是它的实时性,即一边传输一边播 放。MPEG是Motion Picture Experts Group 的缩写,它是国际通用的多媒体压缩编码标准。RTP 协议是IETF 提出的适合...