Reiks的技术博客

C/C++/STL/Algorithm/D3D
posts - 17, comments - 2, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

最大流 Edmonds-Karp

Posted on 2009-08-29 13:39 reiks 阅读(652) 评论(0)  编辑 收藏 引用 所属分类: 算法与数据结构
//Edmonds-Karp
//return the largest flow;flow[] will record every edge's flow
//n, the number of nodes in the graph;cap, the capacity 
//O(VE^2) 
#define N 100
#define inf 0x3f3f3f3f
int Edmonds_Karp(int n,int cap[][N],int source,int sink)
{
    
int flow[N][N];
    
int pre[N],que[N],d[N]; // d 是增广路长度,pre 记录前驱,que是BFS队列
    int p,q,t,i,j;
    
if (source==sink) return inf;
    memset(flow,
0,sizeof(flow));
    
while (true)
    
{
        memset(pre,
-1,sizeof(pre));
        d[source]
=inf;
        p
=q=0, que[q++= source;
        
while(p < q&&pre[sink]<0)    // BFS 找路径
        {
            t
=que[p++];
            
for (i=0;i<n;i++)
                
if ( pre[i]<0 && (j=cap[t][i]-flow[t][i]) ) // j取得残余路径值
                    pre[que[q++= i] = t,d[i] = min(d[t], j);
        }

        
if (pre[sink]<0break;    // 找不到增广路,退出
        for (i=sink; i!=source; i=pre[i])
        
{        
            flow[pre[i]][i]
+=d[sink];    // 正向流量加
            flow[i][pre[i]]-=d[sink];    // 反向流量减
        }

    }

    
for (j=i=0; i<n; j+=flow[source][i++]);
    
return j;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理