Graph G; int dfn[N],low[N],dfscnt; int stack[N],top; int scc[N],scccnt; void tarjan(int u){ dfn[u]=low[u]=++dfscnt;stack[top++]=u; for(int v,i=G.fir[u];i;i=G.nex[i]){ v=G.to[i]; if(!dfn[v]){ tarjan(v); low[u]=std::min(low[u],low[v]); } else if(!scc[v]) low[u]=std::min(low[u],dfn[v]); } if(dfn[u]==low[u]){ scccnt++; do{ scc[stack[--top]]=scccnt; }while(stack[top]^u); } }
Graph G; int dfn[N],low[N],dfscnt; int cut[N]; void tarjan(int u,int root){ dfn[u]=low[u]=++dfscnt; int cnt=0; for(int v,i=G.fir[u];i;i=G.nex[i]){ v=G.to[i]; if(!dfn[v]){ tarjan(v,root); low[u]=std::min(low[v],low[u]); if(low[v]>=dfn[u]&&u!=root) cut[u]=1; cnt++; } low[u]=std::min(low[u],dfn[v]); } if(cnt>1&&u==root) cut[u]=1; }
各种平衡树
可并堆
各种莫队
#define Type int #define _INF _INT_INF int n,m,S,T; Graph G; Type mincost,maxflow,h[N]; int vis[N]; inline void spfa(){ static int que[M*10],left,right; __builtin_memset(h,0x3f,sizeof h); h[S]=0;vis[S]=1; left=0;right=-1;que[++right]=S; int u,i,v; while(left<=right){ u=que[left++];vis[u]=0; for(i=G.fir[u];i;i=G.nex[i]){ v=G.to[i]; if(!G.w[i]||h[v]<=h[u]+G.c[i]) continue; h[v]=h[u]+G.c[i]; if(!vis[v]) que[++right]=v,vis[v]=1; } } } Type dfs(int u,Type want=_INF){ if(u==T) return mincost+=(h[S]-h[T])*want,maxflow+=want,want; vis[u]=1; Type last=want; for(int v,&i=G._fir[u];i;i=G.nex[i]){ v=G.to[i]; if(!G.w[i]||vis[v]||G.c[i]!=h[u]-h[v]) continue; Type k=dfs(v,std::min(last,G.w[i])); G.w[i]-=k;G.w[i^1]+=k;last-=k; if(!last) break; } return want-last; } inline int relable(){ Type d=_INF; for(int i=1;i<=n;i++)if(vis[i]) for(int j=G.fir[i];j;j=G.nex[j])if(G.w[j]&&!vis[G.to[j]]) d=std::min(d,G.c[j]-h[i]+h[G.to[j]]); if(d==_INF) return 0; for(int i=1;i<=n;i++)if(vis[i]) h[i]+=d; return 1; } inline void zkw(){ spfa(); do{ do{ __builtin_memset(vis,0,sizeof vis);__builtin_memcpy(G._fir,G.fir,sizeof G._fir); }while(dfs(S)); }while(relable()); }