最大流（Edmonds-Karp，Dinic，ISAP，Push-Relabel 预流推进算法）

整理的算法模板合集： ACM模板

目录

• $Edmonds-Karp$
• $Dinic$
• $ISAP$
• $Push-Relabel$ 预流推进算法
• • 通用的预流推进算法
  • HLPP 算法

$Edmonds-Karp$

EK 算法的时间复杂度为 O ( n m 2 ) O(nm^2) O(nm2)，一般可以处理 1 0 3 10^3 103 ~ 1 0 4 10 ^4 104的数据

/*luogu P2740草地排水 Edmonds-Karp增广路*/
typedef long long ll;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 2e3+7;
const int M = 5e3+7;int head[N],nex[M],ver[M],tot = 1,edge[M];
int vis[N],incf[N],pre[N];
int n,m,s,t,maxflow;void add(int x,int y,int z){//建正边和反边ver[++tot] = y;edge[tot] = z;nex[tot] = head[x];head[x] = tot;ver[++tot] = x;edge[tot] = 0;nex[tot] = head[y];head[y] = tot;
}bool bfs(){//bfs找增广路memset(vis,0,sizeof vis);queue<int>q;q.push(s);vis[s] = 1;incf[s] = INF;//增广路上各边的最小剩余容量while(q.size()){int x = q.front();q.pop();for(int i = head[x];i;i = nex[i]){if(edge[i]){//只有剩余容量>0才往下走int y = ver[i];if(vis[y])continue;incf[y] = min(incf[x],edge[i]);pre[y] = i;//存前驱，用于找到最长路的实际方案q.push(y);vis[y] = 1;if(y == t)return 1;}}}return 0;
}void update(){//更新增广路及其反向边的剩余容量int x = t;while(x != s){int i = pre[x];edge[i] -= incf[t];edge[i ^ 1] += incf[t];x = ver[i ^ 1];//成对变换}maxflow += incf[t];
}int main(){while(cin>>m>>n){memset(head,0,sizeof head);s = 1,t = n;tot = 1;maxflow = 0;over(i,1,m){int x,

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！