请选择 进入手机版 | 继续访问电脑版

QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 6403|回复: 4

最大流——Ford-Fulkerson算法实现问题

[复制链接]
字体大小: 正常 放大
zyz数模        

6

主题

7

听众

254

积分

升级  77%

  • TA的每日心情
    擦汗
    2014-8-8 17:23
  • 签到天数: 88 天

    [LV.6]常住居民II

    自我介绍
    大一学生,专业环境工程。对数学建模感兴趣。

    群组数学建摸协会

    群组第三届数模基础实训

    群组华南理工大学

    群组2014美赛ICMC题备战群

    发表于 2013-8-17 14:24 |显示全部楼层
    |招呼Ta 关注Ta
    本帖最后由 袁海亮 于 2013-8-17 15:50 编辑

    最大流——Ford-Fulkerson算法实现
    clear,tic
    u=[0 8 0 7 0 0
        0 0 9 5 0 0
        0 0 0 2 0 5
        0 0 0 0 9 0
        0 0 6 0 0 10];
    % u indicates capacity
    f(1,2)=1;f(1,4)=1;f(2,4)=-1;f(2,3)=1;f(3,4)=0;f(3,6)=1;f(4,5)=0; f(5,6)=1;
    % f indicates the current flow
    n=length(u);list=[];maxf(n)=1;
    while maxf(n)>0
        maxf=zeros(1,n);
        pred=zeros(1,n); % 对每个节点j,在该节点可能的增广路上的前一个节点pred(j)
        list=1;record=list;
        maxf(1)=inf; % 沿该可能的增广路到节点j为止可以增广的最大流maxf(j)
        %list是未检查邻接点的标号点,record是已标号点
        while (~isempty(list))&(maxf(n)==0)
            flag=list(1);list(1)=[];   
            label1= find(u(flag,:)-f(flag,:));
            label1=setdiff(label1,record);   
            list=union(list,label1);     
            pred(label1)=flag;     
            maxf(label1)=min(maxf(flag),u(flag,label1)-f(flag,label1));
            record=union(record,label1);
            label2=find(f(:,flag));
            label2=label2';
            label2=setdiff(label2,record);
            list=union(list,label2);
            pred(label2)=-flag;
            maxf(label2)=min(maxf(flag),f(label2,flag));
            record=union(record,label2);  
        end
        if maxf(n)>0   
            v2=n; v1=pred(v2);      
            while v2~=1        
                if v1>0
                    f(v1,v2)=f(v1,v2)+maxf(n);
                else
                    v1=abs(v1);           
                    f(v2,v1)=f(v2,v1)-maxf(n);     
                end
                v2=v1; v1=pred(v2);
            end
        end
    end
    f
    toc
    这个程序是教材上给的,我把u和f的值改了,然后标红的地方原来写的是f(2,4)=1,运算结果为f =

         0     8     0     7     0     0
         0     0     5     3     0     0
         0     0     0     0     0     5
         0     0     0     0     9     0
         0     0     0     0     0    10
    依据题意应该是错误的。
    将其改为f(2,4)=-1,运算结果才为f =
         0     8     0     7     0     0
         0     0     5     2     0     0
         0     0     0     0     0     5
         0     0     0     0     9     0
         0     0     0     0     0    10

    求各位能不能帮忙看看是哪里出了问题,十分感谢。


    zan

    10

    主题

    43

    听众

    1434

    积分

    升级  43.4%

  • TA的每日心情
    奋斗
    2021-8-13 22:51
  • 签到天数: 278 天

    [LV.8]以坛为家I

    自我介绍
    冰E柠檬

    社区QQ达人

    群组2013认证赛A题讨论群组

    群组2013认证赛B题讨论群组

    群组数学建摸协会

    群组2013年数学建模国赛备

    群组高数系列公益培训

      你原文的题意是什么呢?
    给你一个  最大流通用程序,你参考一下吧!

    最大流通用程序.m

    1.68 KB, 下载次数: 21, 下载积分: 体力 -2 点

    回复

    使用道具 举报

    飘逸        

    0

    主题

    7

    听众

    171

    积分

    升级  35.5%

  • TA的每日心情
    奋斗
    2015-12-9 17:10
  • 签到天数: 102 天

    [LV.6]常住居民II

    自我介绍
    一般

    社区QQ达人

    群组学术交流A

    群组2013年国赛B题讨论组

    群组2013年数学建模国赛备

    群组学术交流B

    群组全国大学生数学建模竞

    回复

    使用道具 举报

    0

    主题

    6

    听众

    4

    积分

    升级  80%

    该用户从未签到

    社区QQ达人

    回复

    使用道具 举报

    agathahe 实名认证       

    0

    主题

    1

    听众

    3

    积分

    升级  60%

    该用户从未签到

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2024-3-28 23:30 , Processed in 0.655541 second(s), 85 queries .

    回顶部