上饶建设网站,局域网站点建设方案,邯郸网上销售公司,个人做旅游网站的意义ACM模板 目录概念EK算法Dinic算法概念
yxc老师的部分总结 基本概念 1.1 流网络#xff0c;不考虑反向边 1.2 可行流#xff0c;不考虑反向边 1.2.1 两个条件#xff1a;容量限制、流量守恒 1.2.2 可行流的流量指从源点流出的流量 - 流入源点的流量 1.2.3 最大流是指最大可行…ACM模板 目录概念EK算法Dinic算法概念
yxc老师的部分总结 基本概念 1.1 流网络不考虑反向边 1.2 可行流不考虑反向边 1.2.1 两个条件容量限制、流量守恒 1.2.2 可行流的流量指从源点流出的流量 - 流入源点的流量 1.2.3 最大流是指最大可行流 1.3 残留网络考虑反向边残留网络的可行流f’ 原图的可行流f 原题的另一个可行流 1.4 增广路径 1.5 割 1.5.1 割的定义 1.5.2 割的容量不考虑反向边“最小割”是指容量最小的割。 1.5.3 割的流量考虑反向边f(S, T) c(S, T) 1.5.4 对于任意可行流f任意割[S, T]|f| f(S, T) 1.5.5 对于任意可行流f任意割[S, T]|f| c(S, T) 1.5.6 最大流最小割定理 (1) 流f是最大流 (2) 流f的残留网络中不存在增广路 (3) 存在某个割[S, T]|f| c(S, T) 1.6. 算法 1.6.1 EK O(nm^2) 1.6.2 Dinic O(n^2m) 1.7 应用 1.7.1 二分图 (1) 二分图匹配 (2) 二分图多重匹配 1.7.2 上下界网络流 (1) 无源汇上下界可行流 (2) 有源汇上下界最大流 (3) 有源汇上下界最小流 1.7.3 多源汇最大流 EK算法 链式前向星初始化-1版本 0正边 1反边 S源点 T汇点 d[]流量 pre[]前向边 存图存的是残留网络 时间复杂度O(nm2)O(nm^2)O(nm2) constexpr int N1010,M20010;
int h[N],e[M],ne[M],f[M],idx;
int n,m;
int S,T,flow[N],pre[N];
bool st[N];
void add(int a,int b,int c)
{e[idx]b,f[idx]c,ne[idx]h[a],h[a]idx;e[idx]a,f[idx]0,ne[idx]h[b],h[b]idx;
}
bool bfs()
{queueint q;memset(flow,0x3f,sizeof flow);memset(st,0,sizeof st);q.push(S);st[S]1;while(q.size()){int uq.front();q.pop();for(int ih[u];i!-1;ine[i]){int ve[i];if(f[i]!st[v]){st[v]1;flow[v]min(flow[u],f[i]);pre[v]i;if(vT) return 1;q.push(v);}}}return 0;
}
int EK()
{int ans0;while(bfs()){ansflow[T];for(int iT;i!S;ie[pre[i]^1]){f[pre[i]]-flow[T];f[pre[i]^1]flow[T];}}return ans;
}Dinic算法 模拟队列 时间复杂度O(n2m)O(n^2m)O(n2m) int h[N],e[M],ne[M],f[M],idx;
int S,T,d[N],q[N],cur[N];
void add(int a,int b,int c)
{e[idx]b,ne[idx]h[a],f[idx]c,h[a]idx;e[idx]a,ne[idx]h[b],f[idx]0,h[b]idx;
}
bool bfs()
{memset(d,-1,sizeof d);int hh0,tt0;d[S]0,cur[S]h[S],q[0]S;while(hhtt){int uq[hh];for(int ih[u];i!-1;ine[i]){int ve[i];if(d[v]-1f[i]){d[v]d[u]1;cur[v]h[v];// 当前弧优化if(vT) return 1;q[tt]v;}}}return 0;
}
int dfs(int uS,int flow0x3f3f3f3f)
{if(uT) return flow;int rmnflow;for(int icur[u];i!-1rmn;ine[i]){int ve[i];if(d[v]d[u]1f[i]){int tdfs(v,min(f[i],rmn));if(!t) d[v]-1;// 优化f[i]-t,f[i^1]t,rmn-t;}}return flow-rmn;
}
int dinic()
{int r0;while(bfs()) rdfs();return r;
}
