EK（未完）
以此份代码为例
//P3376 【模板】网络最大流
//EK算法
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=410,M=10010;
int n,m,S,T,h[N],e[M],w[M],ne[M],idx,pre[N],dist[N],st[N],ans,g[N][N];
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
bool bfs(){
memset(st,0,sizeof st);
queue<int> q;
q.push(S);
st[S]=1;
dist[S]=(int)(1e18);
while(q.size()){
int t=q.front();q.pop();
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
if(!w[i]||st[j])continue;
dist[j]=min(dist[t],w[i]);
pre[j]=i;
st[j]=1;
q.push(j);
if(j==T)return 1;
}
}
return 0;
}
void update(){
int cur=T;
while(cur!=S){
int i=pre[cur];
w[i]-=dist[T];
w[i^1]+=dist[T];
cur=e[i^1];
}
ans+=dist[T];
}
signed main(){
memset(h,-1,sizeof h);
cin>>n>>m>>S>>T;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
if(g[a][b])w[g[a][b]-2]+=c;
else{
add(a,b,c);
add(b,a,0);
g[a][b]=idx;
}
}
while(bfs())update();
cout<<ans;
} //by yjx
EK算法单次bfs复杂度为 \(O(m)\)。
Dinic（未完）
#include<bits/stdc++.h>
#define fir first
#define se second
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
template <typename type>
inline void read(type &x) {
x=0; bool f=0; char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
if(f) x=-x;
}
template <typename type,typename ...t>
inline void read(type &x,t &...te) {read(x); read(te...);}
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=210,M=1e4+50;
int n,m;
int head[N],nxt[M],to[M],W[M],num=1;
int S,T;
void add(int u,int v,int w) {
++num; nxt[num]=head[u]; to[num]=v; W[num]=w; head[u]=num;
++num; nxt[num]=head[v]; to[num]=u; W[num]=0; head[v]=num;
}
int cur[N],dep[N];
bool bfs() {
memset(dep,-1,sizeof(dep));
queue<int>q;
q.push(S);
cur[S]=head[S];
dep[S]=1;
while(!q.empty()) {
int u=q.front(); q.pop();
for(int i=head[u];i;i=nxt[i]) {
int v=to[i];
if(W[i]&&dep[v]==-1) {
dep[v]=dep[u]+1;
cur[v]=head[v];
if(v==T) return true;
q.push(v);
}
}
}
return false;
}
ll dfs(int u,ll lim) {
ll flow=0;
if(u==T) return lim;
for(int i=cur[u];i&&flow<lim;i=nxt[i]) {
int v=to[i];
cur[u]=i;
if(W[i]&&dep[v]==dep[u]+1) {
ll t=dfs(v,min(lim-flow,W[i]));
if(!t) dep[v]=-1;
W[i]-=t;
W[i^1]+=t;
flow+=t;
}
}
return flow;
}
int dinic() {
int ans=0,flow;
while(bfs())
while(flow=dfs(S,0x3f3f3f3f))
ans+=flow;
return ans;
}
signed main() {
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
read(n,m,S,T);
for(int i=1;i<=m;i++) {
int u,v,w;
read(u,v,w);
add(u,v,w);
}
printf("%lld",dinic());
return 0;
}
Dinic算法单次bfs复杂度为 \(\text{O}(m)\)
增广轮数<=n
单轮增广复杂度 \(\text{O}(nm)\)
下面我们来证明dinic增广轮数<=n
首先dinic会按照层数分层，将长度最短的增广路径全部删除，因此进行一遍dfs后，S到T在残量网络上的距离将会改变。
现在我们证明每一次S到T在残量网络上的距离将会增加1
设此时S到u经过若干条边后联通，S经过若干条边与v联通且dis(S,v)>dis(S,u)距离（不联通也是相同道理，相当于在不经过u的情况下S到v的距离为INF），v经过若干条边与T联通，且S->u->v->T是最短的一条增广路径，而u->v是增广路径上边权最小的边。
经过一遍增广后，此时残量网络会变成这样
此时S->u->v->T不联通，而dis(S,v)>dis(S,u)，因此添加v->u边并不会让S到T的距离更小。
因此只会让S->T距离增大，且至少增加1。又因为dis(S,T)最大为n，因此增广轮数最多为n。
下面我们来证单轮增广复杂度 \(\text{O}(nm)\)
首先每次推流会清空至少一条边u->v，而此时添加的反向边不满足dep[v]==dep[u]+1，因此最多清空 \(\text{O}(m)\) 次，对于清空每一条边需要找到一条他所对应的增广路，此时最多从S访问到T，因此总复杂度为 \(\text{O}(mn)\)。
因此Dinic复杂度为 \(O(n^2m)\)。
（从复杂度分析就可很显然地看出，Dinic复杂度在正常题目建图情况下达不到该上界，因此总是跑得飞快）
by lyk
借鉴了[该地址](Dinic算法复杂度证明 | yukiyama (iyukiyama.github.io))内容
标签：cur,增广,int,复杂度,网络,证明,dep,num From： https://www.cnblogs.com/classblog/p/18250979