首页 > 代码库 > Net FLow Template

Net FLow Template

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 = http://www.mamicode.com/1, des = n;>