网络流Ek算法网络流Ek算法

例题:Flow Problem HDU - 3549
Edmonds_Karp算法其实是不断找增广路的过程.
但是在找的过程中是找"最近"的一天增广路,
而不是找最高效的一条增广路,
而且还会重复找,
所以复杂度也是爆表的,很容易被卡. 所以有Dinic和ISAP这两个更加优秀的算法.
我的板子

struct Edge { int lst, from, to, cap, flow; Edge () { } Edge (intll, int ff, int tt, int cc, int fff) : lst(ll), from(ff), to(tt), cap(cc), flow(fff) { } }; const int maxn = 1024; const intinf = 0x3f3f3f3f; class Edmonds_karp { public: Edge edge[maxn*2]; int head[maxn]; int cn, cm; int csz; int path[maxn]; int deta[maxn]; void init(int n, int m) { cn = n; cm = m; memset(head, 0, sizeof(head)); csz = 2; // 注意这儿应该是偶数开始因为奇数^1等价于减1 偶数^1等价于加一. // 因为我前向星是以0为结尾的所以我必须从2开始. }void add(int u, int v, int c) { edge[csz] = Edge(head[u], u, v, c, 0); head[u]= csz++; edge[csz] = Edge(head[v], v, u, 0, 0); // 反向边,记得容量为0, 但是有些情况是可以修改的. 例如在建无向图的时候. head[v]= csz++; }int maxflow(int st, int ed) { int res = 0; int i, u, v, cap, flow; while (true) { // 找增广路 memset(deta, 0, sizeof(deta)); queue q; q.push(st); deta[st] = inf; while (!q.empty()) { u = q.front(); q.pop(); for (i=head[u]; i; i=edge[i].lst) { v = edge[i].to; cap = edge[i].cap; flow = edge[i].flow; if (!deta[v] && cap > flow) {// 该点未被增广, 同时可流 deta[v] = min(deta[u], cap - flow); // 限流 path[v] = i; // 记录路径 q.push(v); } } if (deta[ed]) break; // 找到一条增广路了. } if (!deta[ed])break; // 如果找不到增广路就说明最大流了,结束. for (i=path[ed]; i!=path[st]; i=path[edge[i].from]) {// 更新残量图 edge[i].flow += deta[ed]; edge[i^1].flow -= deta[ed]; } res += deta[ed]; } return res; } }Ek;

紫书模板:

struct Edge { int from, to, cap, flow; Edge (int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) { } }; struct EdmondsKarp { int n, m; vector edges; vectorG[maxn]; int a[maxn]; int p[maxn];

void init(int n) {
this->n = n;
for (int i=0; i<=n; ++i) G[i].clear(), edges.clear();
}

void add(int u, int v , int val) { edges.push_back(Edge(u, v, val, 0)); edges.push_back(Edge(v, u, 0, 0)); m = edges.size(); G[u].push_back(m-2); G[v].push_back(m-1); }int Maxflow(int s, int t) { int flow = 0; while (1) { memset(a, 0, sizeof(a)); queue Q; Q.push(s); a[s] = inf; while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i=0; i e.flow) { p[e.to] = G[x][i]; a[e.to] = min(a[x], e.cap - e.flow); Q.push(e.to); } } if (a[t]) break; } if (!a[t]) break; for (int u = t; u!=s; u =edges[p[u]].from) { edges[p[u]].flow += a[t]; edges[p[u]^1].flow -= a[t]; } flow += a[t]; } return flow; } }Ek;

【网络流Ek算法】转载于:https://www.cnblogs.com/cgjh/p/9497453.html