Net FLow Template

浏览数：27 / 时间：2015年06月09日

EK  Template :

bool bfs(int src, int des){
    memset(pre, -1, sizeof(pre));
    while(!que.empty()) que.pop();
    pre[src] = 0;
    int index;
    que.push(src);
    while(!que.empty()){
        index = que.front();
        que.pop();
        for(int i = src; i <= des; ++i){
            if(pre[i] == -1 && map[index][i] > 0){
                pre[i] = index;
                if(i == des)    return true;
                que.push(i);
            }
        }
    }
    return false;
}

int MaxFlow(int src, int des){
    int maxflow = 0;
    while(bfs(src, des)){
        int minflow = INF;
        int i;
        for(i = des; i != src; i = pre[i])  
            minflow = min(minflow, map[pre[i]][i]);
        for(i = des; i != src; i = pre[i]){
            map[pre[i]][i] -= minflow;
            map[i][pre[i]] += minflow;
        }
        maxflow += minflow;
    }
    return maxflow;
}

SAP + GAP  Template :

int sap(int u,int flow){
    if(u == src) return flow;
    int ans = 0, i, t;
    for(i = src; i <= des; ++i)
        if(map[u][i] && dis[u] == dis[i] + 1){
            t = sap(i, min(flow - ans, map[u][i]));
            map[u][i] -= t, map[i][u] += t,ans += t;
            if(ans == flow) return ans;
        }
    if(dis[src] >= n + 2) return ans;
    if(!--gap[dis[u]]) dis[src] = n + 2;
    ++gap[++dis[u]];
    return ans;
}
	src = 1, des = n;
	for(gap[0] = n + 2; dis[src] < n + 2; )
        ans += sap(src,INF);

　　

 

Net FLow Template,古老的榕树,5-wow.com

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： des class style src log ha for si des class style src log ha for si

相关文章

随机文章

您可能还喜欢

您可能还喜欢