平时写的Dinic费用流复杂度是多少?有更优的费用流算法吗?
我写的Dinic:
int bfs(){
for(int i=1;i<=n+1;i++) d[i]=INF,vis[i]=0;
queue<int>q;q.push(S);d[S]=0;
while(!q.empty()){
int u=q.front();
q.pop();
cur[u]=head[u];vis[u]=0;
for(int i=head[u];i;i=e[i].nxt){
int y=e[i].to;
if(d[y]>d[u]+e[i].c&&e[i].w){
d[y]=d[u]+e[i].c;
if(!vis[y]){
vis[y]=1;
q.push(y);
}
}
}
}
return (d[T]!=INF);
}
int dfs(int x,int flow){
if(flow==0||x==T) return flow;
int res=flow;vis[x]=1;
for(int i=cur[x];i;i=e[i].nxt){
int y=e[i].to;cur[x]=i;
if(!vis[y]&&d[y]==d[x]+e[i].c&&e[i].w){
int tmp=dfs(y,min(res,e[i].w));
if(tmp==0) d[y]=-INF;
e[i].w-=tmp;e[i^1].w+=tmp;res-=tmp;
cost+=tmp*e[i].c;
}
}
return flow-res;
}
int flow=0,maxflow=0;
while(bfs())
while(flow=dfs(S,INF)) maxflow+=flow;