Chinaunix首页 | 论坛 | 博客
  • 博客访问: 326300
  • 博文数量: 78
  • 博客积分: 2536
  • 博客等级: 少校
  • 技术积分: 600
  • 用 户 组: 普通用户
  • 注册时间: 2008-04-29 01:50
文章分类

全部博文(78)

文章存档

2011年(1)

2010年(17)

2009年(52)

2008年(8)

我的朋友

分类: C/C++

2009-10-01 23:41:51

1.    最大流最小割定理介绍:

把一个流网络的顶点集划分成两个集合S和T,使得源点s ∈S且汇点t ∈T,割(S,T)的容量C(S,T) =∑Cuv, 其中u∈S且v∈T。

从直观上看,截集(S,T)是从源点s到汇点t的必经之路,如果该路堵塞则流从s无法到达t。于是我们可以得到下面的定理:

 

最大流最小割定理:

任意一个流网络的最大流量等于该网络的最小的割的容量。

 

这个定理的证明这里就不给出了,可以参考图论方面的资料。

 

2.    求最大流的Edmonds-Karp算法简介:

 

若给定一个可行流F=(Fij),我们把网络中使Fij=Cij的弧称为饱和弧,Fij

 

Edmonds-Karp算法的伪代码如下:

 

设队列Q--存储当前未检查的标号点,队首节点出队后,成为已检查的标点;

path -- 存储当前已标号可改进路经;

 

repeat

       path置空;

       源点s标号并进入path和Q;

       while  Q非空  and  汇点t未标号 do

              begin

                     移出Q的队首顶点u;

                     for 每一条从u出发的弧(u,v) do

                            if  v未标号 and 弧(u,v)的流量可改进

then v进入队列Q和path;

              end while

       if 汇点已标号

then 从汇点出发沿着path修正可改进路的流量;

until 汇点未标号;

 

Edmonds-Karp算法有一个很重要的性质:当汇点未标号而导致算法结束的时候,那些已经标号的节点构成集合S,未标号的节点构成集合T,割(S,T)恰好是该流网络的最小割;且这样求出的最小割(S,T)中集合S的元素数目一定是最少的。

 

寻找最大流的基本方法是Ford-Fulkerson方法,该方法有多种实现,其基本思想是从某个可行流F出发,找到关于这个流的一个可改进路经 P,然后沿着P调整F,对新的可行流试图寻找关于他的可改进路经,如此反复直至求得最大流。现在要找最小费用的最大流,可以证明,若F是流量为V(F)的 流中费用最小者,而P是关于F的所有可改进路中费用最小的可改进路,则沿着P去调整F,得到的可行流F'一定是流量为V(F')的所有可行流中的最小费用 流。这样,当F是最大流时候,他就是所要求的最小费用最大流。

 

注意到每条边的单位流量费用B(i,j)≥0,所以F=0必是流量为0的最小费用流,这样总可以从F=0出发求出最小费用最大流。一般的,设已知F 是流量V(F)的最小费用流,余下的问题就是如何去寻找关于F的最小费用可改进路。为此我们将原网络中的每条弧变成两条方向相反的 弧:

 

1。前向弧,容量C和费用B不变,流量F为0;

2。后向弧,容量C为0,费用为-B,流量F为0;

 

每一个顶点上设置一个参数CT,表示源点至该顶点的通路上的费用和。如果我们得出一条关于F的最小费用可改进路时,则该路上的每一个顶点的CT值相对于其它可改进路来说是最小的。每一次寻找最小费用可改进路时前,源点的CT为0,其它顶点的CT为+∞。

 

设cost为流的运输费用,初始时由于F=0,则cost=0,我们每求出一条关于F的最小费用可改进路,则通过cost ← cost + ∑B(e)*d, (其中e∈P,d为P的可改进量)来累积流的运输费用的增加量。

 

显然,当求出最小费用最大流时,cost便成为最大流的运输费用了。

 

另外设置布尔变量break为最小费用可改进路的延伸标志,在搜索了网络中的每一个顶点后,若break=true表示可改进路还可以延伸,还需要重新搜索网络中的顶点;否则说明最小费用的可改进路已经找到或者最大流已经求出。

 

 

 

本人说明:

 

这个模版的代码完全按照BFS从源点逐个遍历增广路径,得到最大增广容量,通过不断调整,最后求得最大流量,值得注意的是,最后一次BFS后所标的路线即为最小截集,即所谓的瓶颈,据此很容易求出最小截集的容量。

 

 

 

#include <iostream>
#include 
<queue>
using namespace std;
//邻接阵实现
const long MAXN=1000;
const long lmax=0x7FFFFFFF;
long Net[MAXN][MAXN];//残余网络
long Path[MAXN];//增广路径
long Lv[MAXN];//增广路径通过容量
queue<long> q;
long m,n;//点,边
long Start,End;

void init()
{
    
while (!q.empty())
    
{
        q.pop();
    }

    memset(Path,
-1,sizeof(Path));
}


long Min(long a,long b)
{
    
return a<b?a:b;
}


long bfs()
{
    init();
    Path[Start]
=0;
    Lv[Start]
=lmax;

    q.push(Start);

    
while (!q.empty())
    
{
        
long t=q.front();
        q.pop();

        
if (t==End)
        
{
            
break;
        }


        
long i;
        
for (i=1;i<=m;++i)
        
{
            
if (i!=Start&&Path[i]==-1&&Net[t][i])
            
{
                Lv[i]
=Min(Lv[t],Net[t][i]);
                q.push(i);
                Path[i]
=t;
            }

        }

    }


    
if (Path[End]==-1)
    
{
        
return -1;
    }


    
return Lv[m];
}


void print(long n)
{
    printf(
"%ld\n",n);
}


void Ford_Fulkerson()
{
    
long i;
    
long Max_Flow=0;


    
for (i=0;i<n;++i)
    
{
        
long from,to,cost;
        scanf(
"%ld %ld %ld",&from,&to,&cost);
        Net[from][to]
=cost;//cost为剩余量
        
//如果在现有网络上扩展 剩余量为容量-已占用量
        
//最大流结果要加上已流入的量
    }


    scanf(
"%ld %ld",&Start,&End);

    
long step;
    
while ((step=bfs())!=-1)//反搜增广路径并调整流量
    {
        Max_Flow
+=step;
        
long now=End;
        
while (now!=Start)
        
{
            
long pre=Path[now];
            Net[pre][now]
-=step;
            Net[now][pre]
+=step;
            now
=pre;
        }

    }


    print(Max_Flow);
}




int main()
{

    
while (scanf("%ld %ld",&m,&n)!=EOF)
    
{
        Ford_Fulkerson();
    }

    
return 0;
}
阅读(787) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~