首页 > 代码库 > 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;>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。