职业IT人-IT人生活圈

 找回密码
 成为会员
搜索
查看: 765|回复: 0

解释C++dinic程序

[复制链接]
开平车迷网 发表于 2009-8-18 10:55 | 显示全部楼层 |阅读模式
bool build()//建立层次图
{
int x,y;
memset(d,-1,sizeof(d));
memset(G,-1,sizeof(G));
op=cl=d=0;line[cl++]=s;G=g;
while(op<cl)
{
x=line[op++];
for(int i=g[x];i+1;i=np)
{
y=to;
if(cap&&d[y]==-1)
{
d[y]=d[x]+1;G[y]=g[y];
if(y==t)return true;
line[cl++]=y;
}
}
}
return false;
}

int find(int x,int low=inf)//进行增广
{
if(x==t)return low;
int ret=0,y;
for(int &i=G[x];i+1;i=np)//注意i是引用
{
y=to;
if(cap && d[y]==d[x]+1 && (ret=find(y,low<?cap)))
{
cap-=ret;cap[vp]+=ret;
return ret;
}
}
return 0;
}

int dinic()//主过程
{
int flow,ret=0;
while(build())
while(flow=find(s))cnt+=flow;
return ret;//这里返回0阿


}
请求解释
不用很详细
我能看懂就行了
主要是各个数组是用来干什么的啊?
好的加40-80分!
您需要登录后才可以回帖 登录 | 成为会员

本版积分规则

QQ|手机版|小黑屋|网站帮助|职业IT人-IT人生活圈 ( 粤ICP备12053935号-1 )|网站地图
本站文章版权归原发布者及原出处所有。内容为作者个人观点,并不代表本站赞同其观点和对其真实性负责,本站只提供参考并不构成任何投资及应用建议。本站是信息平台,网站上部分文章为转载,并不用于任何商业目的,我们已经尽可能的对作者和来源进行了通告,但是能力有限或疏忽造成漏登,请及时联系我们,我们将根据著作权人的要求立即更正或者删除有关内容。

GMT+8, 2024-3-29 14:49 , Processed in 0.105327 second(s), 20 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表