谁有dinic的资料和PASCAL程序?

Dinic算法
来自"NOCOW"
在10:19 2007年7月23日由Dd engi (Talk | 贡献)所做的修订版本
(差异) ←更早版本 | 查看当前版本 (差异) | 更新版本→ (差异)
跳转到: 导航, 搜索
目录 [隐藏]
1 算法介绍
1.1 层次图
2 算法流程
3 时间复杂度
4 代码实现
4.1 递归实现
4.2 非递归实现

算法介绍
层次图
层次图，就是把原图中的点按照到到源的距离分“层”，只保留不同层之间的边的图。

算法流程
根据残量网络计算层次图。
在层次图中使用DFS进行增广直到不存在增广路
重复以上步骤直到无法增广
时间复杂度
代码实现
递归实现
代码简短，效率略低。

bool build()//建立层次图
{
int x,y;
memset(d,-1,sizeof(d));
memset(G,-1,sizeof(G));
bg=ed=d[s]=0;Q[ed++]=s;G[s]=g[s];
while(bg<ed)
{
x=Q[bg++];
for(int i=g[x];i+1;i=np[i])
{
y=to[i];
if(cap[i]&&d[y]==-1)
{
d[y]=d[x]+1;G[y]=g[y];
if(y==t)return true;
Q[ed++]=y;
}
}
}
return false;
}

int find(int x,int low=inf)//进行增广
{
if(x==t)return low;
int ret=0,y;
f