本文主要是介绍网络最大流增广路模板(EK Dinic)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
EK算法：
int fir[maxn];
int u[maxm],v[maxm],cap[maxm],flow[maxm],nex[maxm];
int e_max;
int p[maxn],q[maxn],d[maxn];void add_edge(int _u,int _v,int _w)
{int e;e=e_max++;u[e]=_u;v[e]=_v;cap[e]=_w;nex[e]=fir[u[e]];fir[u[e]]=e;e=e_max++;u[e]=_v;v[e]=_u;cap[e]=0;nex[e]=fir[u[e]];fir[u[e]]=e;
}int max_flow(int s,int t)
{memset(flow,0,sizeof flow);int total_flow=0;for (;;){memset(d,0,sizeof d);d[s]=INF;int f=0,r=0;q[0]=s;while (f<=r){int _u=q[f++];for (int e=fir[_u];~e;e=nex[e]){if (!d[v[e]] && cap[e]>flow[e]){q[++r]=v[e];p[v[e]]=e;d[v[e]]=min(d[u[e]],cap[e]-flow[e]);}}}if (d[t]==0) break;for (int e=p[t];;e=p[u[e]]){flow[e]+=d[t];flow[e^1]-=d[t];if (u[e]==s) break;}total_flow+=d[t];}return total_flow;
}Dinic算法（效率远高于EK算法）：
int fir[maxn];
int u[maxm],v[maxm],cap[maxm],flow[maxm],nex[maxm];
int e_max;
int iter[maxn],q[maxn],lv[maxn];void add_edge(int _u,int _v,int _w)
{int e;e=e_max++;u[e]=_u;v[e]=_v;cap[e]=_w;nex[e]=fir[u[e]];fir[u[e]]=e;e=e_max++;u[e]=_v;v[e]=_u;cap[e]=0;nex[e]=fir[u[e]];fir[u[e]]=e;
}void dinic_bfs(int s)
{int f,r;memset(lv,-1,sizeof lv);q[f=r=0]=s;lv[s]=0;while(f<=r){int x=q[f++];for (int e=fir[x];~e;e=nex[e]){if (cap[e]>flow[e] && lv[v[e]]<0){lv[v[e]]=lv[u[e]]+1;q[++r]=v[e];}}}
}int dinic_dfs(int _u,int t,int _f)
{if (_u==t) return _f;for (int &e=iter[_u];~e;e=nex[e]){if (cap[e]>flow[e] && lv[_u]<lv[v[e]]){int _d=dinic_dfs(v[e],t,min(_f,cap[e]-flow[e]));if (_d>0){flow[e]+=_d;flow[e^1]-=_d;return _d;}}}return 0;
}int max_flow(int s,int t)
{memset(flow,0,sizeof flow);int total_flow=0;for (;;){dinic_bfs(s);if (lv[t]<0) return total_flow;memcpy(iter,fir,sizeof iter);int _f;while ((_f=dinic_dfs(s,t,INF))>0)total_flow+=_f;}return total_flow;
}这篇关于网络最大流增广路模板(EK Dinic)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
