| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1141 人关注过本帖
标题:请教关于网络流的问题
只看楼主 加入收藏
keloy
Rank: 2
等 级:论坛游民
帖 子:107
专家分:16
注 册:2007-9-27
收藏
 问题点数:0 回复次数:4 
请教关于网络流的问题
关于网络最大流的实现,小弟知道网络流在是通过找到每个图里面的的一个s-t的最大的流,然后再扩充路径得到一个余图,再查找余图中的一个s-t的最大流,直到没有为止,而且知道最大剪切定理在证明最大留的正确性。
但是小弟一直没想明白的是怎么用广搜的策略来得到一个最大流,看了很多的代码的都没有看出广搜策略是怎么实现的。主要是没有注释和实例,如果哪位大侠回我的贴的话,请给个实例吧,只要清楚就可以了,不需要太难的,谢谢了…………
搜索更多相关主题的帖子: 网络流 余图中 定理 
2008-03-24 22:07
feier7501
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2007-12-6
收藏
得分:0 
网络上好像没有这个算法的实现
/*find函数里的就是bfs的过程,这个程序是我今天刚完成的,可能有错误,但是我测试了一下并没有错误*/
#include <stdio.h>
#include <string.h>
#include <limits.h>
const SIZE=20;
struct node {
    int father,index;
};
struct queue {
    int head,tail;
    node n[SIZE];
};
struct ARC {
    int cap,now;
};
struct graph {
    ARC arc[SIZE][SIZE];
    int ArcNum;
    int src,dest;
    int max;
    void init();
    int find(int &min);
    int maxflow();
};
void graph::init()
{
    scanf("%d",&ArcNum);
    int i,j,k,c;
    for(i=0;i<SIZE;i++)
        for(j=0;j<SIZE;j++)
            arc[i][j].cap=arc[i][j].now=0;        
    for(k=0;k<ArcNum;k++)
    {
        scanf("%d %d %d",&i,&j,&c);
        arc[i][j].cap=c;
    }
    max=0;
}
int graph::find(int &min)
{
    int visited[SIZE],i,j;
    queue q;
    q.head=q.tail=-1;
    q.tail++;
    q.n[q.tail].index=src;
    q.n[q.tail].father=0;
    memset(visited,0,sizeof(visited));
    visited[src]=1;
    while(q.head < q.tail && q.tail<SIZE)
    {
        int j=q.n[++q.head].index;
        for(i=1;i<SIZE;i++)
        {
            if(arc[j][i].cap && (arc[j][i].cap-arc[j][i].now) && !visited[i] && i!=dest)
            {
                visited[i]=1;
                q.tail++;
                q.n[q.tail].father=q.head;
                q.n[q.tail].index=i;
            }
            else if(arc[j][i].cap && (arc[j][i].cap-arc[j][i].now) && !visited[i] && i==dest)
            {
                visited[i]=1;
                q.tail++;
                q.n[q.tail].father=q.head;
                q.n[q.tail].index=i;
                int k=q.tail,kf=q.n[k].father,f=q.n[kf].index,c=q.n[k].index;
                min=INT_MAX;
                while(c!=src)
                {
                    if(arc[f][c].cap-arc[f][c].now < min)
                        min=arc[f][c].cap-arc[f][c].now;                    
                    c=f;
                    kf=q.n[kf].father;
                    f=q.n[kf].index;                    
                }
                f=q.tail;
                c=q.n[f].index;
                if(min>0)
                {
                    max+=min;
                    while(f)
                    {
                        arc[f][c].now+=min;
                        f=q.n[f].father;
                        c=q.n[f].index;
                    }
                    return 1;
                }
                else
                    return 0;
            }
        }
    }
}
int graph::maxflow()
{
    scanf("%d %d",&src,&dest);
    int min,i;
    for(i=0;i<10;i++)
        if(find(min) && min>=0)
            continue;
        else if(min<=0)
            break;

    return max;
}
int main()
{
    graph g;
    g.init();
    printf("%d\n",g.maxflow());
    return 0;
}
/*
测试数据:
input:
11
1 2 6
1 3 9
1 4 5
2 5 4
3 5 5
3 6 4
4 6 4
5 6 4
5 7 15
6 2 6
6 7 6
1 7
output:15
*/
2008-03-25 20:55
feier7501
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2007-12-6
收藏
得分:0 
改正一下
int graph::maxflow()
{
    scanf("%d %d",&src,&dest);
    int min,i;
    for(i=0;i<10;i++)
        if(find(min) && min>=0)
            continue;
        else if(min<0)//此处改一下
            break;

    return max;
}
2008-03-25 20:57
feier7501
Rank: 1
等 级:新手上路
帖 子:23
专家分:0
注 册:2007-12-6
收藏
得分:0 
再改一下
int graph::maxflow()
{
    scanf("%d %d",&src,&dest);
    int min,i;    
    while(find(min));    

    return max;
}
这样应该没问题了。
2008-03-25 21:06
keloy
Rank: 2
等 级:论坛游民
帖 子:107
专家分:16
注 册:2007-9-27
收藏
得分:0 
谢谢了,我还得慢慢的看,不过谢谢了……
2008-03-25 22:13
快速回复:请教关于网络流的问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.036137 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved