省选模板

• tarjan 缩强连通分量

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);
	}
}

• tarjan 求割点

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());
}