- 在线时间
- 48 小时
- 最后登录
- 2014-8-8
- 注册时间
- 2013-5-18
- 听众数
- 7
- 收听数
- 2
- 能力
- 0 分
- 体力
- 645 点
- 威望
- 0 点
- 阅读权限
- 30
- 积分
- 254
- 相册
- 0
- 日志
- 0
- 记录
- 1
- 帖子
- 122
- 主题
- 6
- 精华
- 0
- 分享
- 0
- 好友
- 26
升级 77% TA的每日心情 | 擦汗 2014-8-8 17:23 |
---|
签到天数: 88 天 [LV.6]常住居民II
- 自我介绍
- 大一学生,专业环境工程。对数学建模感兴趣。
群组: 数学建摸协会 群组: 第三届数模基础实训 群组: 华南理工大学 群组: 2014美赛ICMC题备战群 |
本帖最后由 袁海亮 于 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
|