模板库-图论
图论
邻接表
struct Graph{
int fir[N],nex[M],to[M],tot;
inline void add(int u,int v,int flag=1){
to[++tot]=v;nex[tot]=fir[u];fir[u]=tot;
if(flag) add(v,u,0);
}
inline void clear(){std::memset(fir,0,sizeof fir);tot=0;}
}G;
dij 最短路
inline void dij(int u,int *dis,const Graph &G=::G){
std::memset(dis,0x3f,(n+1)*sizeof dis[0]);dis[u]=0;
static std::priority_queue >que;
que.push(std::make_pair(0,u));
while(!que.empty()){
u=que.top().second;
if(que.top().first^(-dis[u])){que.pop();continue;}
que.pop();
for(int v,i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(dis[v]<=dis[u]+G.w[i]) continue;
dis[v]=dis[u]+G.w[i];que.push(std::make_pair(-dis[v],v));
}
}
}
tarjan 缩强连通分量
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 求割点
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;
}
tarjan 求桥
void tarjan(int u){
dfn[u]=low[u]=++dfscnt;
for(int v,i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(!dfn[v]){
fa[v]=u;tarjan(v);
low[u]=std::min(low[u],low[v]);
if(low[v]>dfn[u]) bridge[v]=1,ans++;
}
else if(v!=fa[u]) low[u]=std::min(low[u],dfn[v]);
}
}
st 表 \(O(n\log n)-O(1)\) 求 LCA
struct Graph{
int fir[N],nex[M],to[M],tot;
inline void add(int u,int v,int c,int flag=1){
to[++tot]=v;nex[tot]=fir[u];fir[u]=tot;
if(flag) add(v,u,0);
}
int st[20][N*2],log2[N*2];
int dfscnt,dfn[N],id[N*2];
int deep[N];
void dfs(int u,int fa=0){
deep[u]=deep[fa]+1;dfn[u]=++dfscnt;id[dfscnt]=u;
for(int v,i=fir[u];i;i=nex[i]){
v=to[i];
if(v==fa) continue;
sum[v]=sum[u]+w[i];
dfs(v,u);id[++dfscnt]=u;
}
}
inline int getLca(int u,int v){
if(dfn[u]>dfn[v]) lib::swap(u,v);
u=dfn[u];v=dfn[v];
int len=log2[v-u+1];
return deep[st[len][u]]>1]+1,st[0][i]=id[i];
for(int j=1;j<19;j++)for(int i=1;i+(1< 重链剖分
struct Graph{
int fir[N],nex[M],to[M],tot;
inline void add(int u,int v,int flag=1){
to[++tot]=v;
nex[tot]=fir[u];fir[u]=tot;
if(flag) add(v,u,0);
}
inline void clear(){std::memset(fir,0,sizeof fir);tot=0;}
}G;
int n;
int size[N],deep[N],fa[N];
int son[N],dfscnt,dfn[N],top[N];
void dfs1(int u){
size[u]=1;
for(int v,i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(v==fa[u]) continue;
fa[v]=u;deep[v]=deep[u]+1;
dfs1(v);
size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
}
}
void dfs2(int u,int topnow=1){
top[u]=topnow;dfn[u]=++dfscnt;
if(!son[u]) return;
dfs2(son[u],topnow);
for(int i=G.fir[u];i;i=G.nex[i])if(!dfn[G.to[i]]) dfs2(G.to[i],G.to[i]);
}
dinic
int n,m,S,T;
int deep[N];
int left,right,que[N];
inline int bfs(){
std::memset(deep,0,(n+1)*sizeof deep[0]);
left=right=0;
que[0]=S;deep[S]=1;
int u;
while(left<=right){
u=que[left++];
for(int v,i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(deep[v]||!G.w[i]) continue;
deep[v]=deep[u]+1;que[++right]=v;
if(v==T) return 1;
}
}
return 0;
}
long long dfs(int u,long long now=1e18){
if(u==T) return now;
long long res=now;
for(int v,&i=G.fir_[u];i;i=G.nex[i]){
v=G.to[i];
if(deep[v]!=deep[u]+1||!G.w[i]) continue;
long long k=dfs(v,std::min(res,G.w[i]));
if(!k) deep[v]=0;
else G.w[i]-=k,G.w[i^1]+=k,res-=k;
if(!res) break;
}
return now-res;
}
inline long long dinic(){
long long ans=0;
while(bfs()){
long long now;
std::memcpy(G.fir_,G.fir,(n+1)*sizeof G.fir[0]);
while(now=dfs(S)) ans+=now;
}
return ans;
}
最小费用最大流（放错了，本来应该是普通费用流，放成 zkw 了）
int n,S,T;
int mincost,maxflow,h[N];
int vis[N];
inline void spfa(){
static int que[M*10],left,right;
__builtin_memset(h,0x3f,sizeof h);
h[T]=0;vis[T]=1;
left=0;right=-1;que[++right]=T;
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;
}
}
}
int dfs(int u,int want=_INT_INF){
if(u==T) return mincost+=(h[S]-h[T])*want,maxflow+=want,want;
vis[u]=1;
int 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;
int k=dfs(v,lib::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(){
int d=_INT_INF;
for(int i=_INT_INF;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]]) lib::chkMin(d,G.c[j]-h[i]+h[G.to[j]]);
if(d==_INT_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());
}
zkw 费用流（能带有负权）：https://artofproblemsolving.com/community/c1368h1020435
int n,m,S,T;
int 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;
}
}
}
int dfs(int u,int want=_INT_INF){
if(u==T) return mincost+=(h[S]-h[T])*want,maxflow+=want,want;
vis[u]=1;
int 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;
int k=dfs(v,lib::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(){
int d=_INT_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]]) lib::chkMin(d,G.c[j]-h[i]+h[G.to[j]]);
if(d==_INT_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());
}
有源汇上下界最大流
long long d[N];
inline void add(int u,int v,long long l,long long r){
G.add(u,v,r-l);
d[u]-=l;d[v]+=l;
}
int main(){
int s=n+1,t=s+1;
S=t+1;T=S+1;
long long sum=0;
for(int i=1;i<=t;i++){
if(d[i]>0) G.add(S,i,d[i]),sum+=d[i];
else if(d[i]<0) G.add(i,T,-d[i]);
}
G.add(t,s,LL_INF);
if(dinic()^sum) puts("-1\n");
else{
for(int i=G.fir[S];i;i=G.nex[i]) G.w[i]=G.w[i^1]=0;
for(int i=G.fir[T];i;i=G.nex[i]) G.w[i]=G.w[i^1]=0;
sum=G.w[G.tot];G.w[G.tot]=G.w[G.tot-1]=0;
S=s;T=t;
printf("%lld\n\n",sum+dinic());
}
return 0;
}
最小割树
Graph G,T;
struct Flow{
int S,T;
int deep[N];
int left,right,que[N];
inline int bfs(){
std::memset(deep,0,sizeof deep);
left=right=0;
que[0]=S;deep[S]=1;
int u;
while(left<=right){
u=que[left++];
for(int v,i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(deep[v]||!G.w[i]) continue;
deep[v]=deep[u]+1;que[++right]=v;
if(v==T) return 1;
}
}
return 0;
}
int dfs(int u,int now=INT_INF){
if(u==T) return now;
int res=now;
for(int v,&i=G.fir_[u];i;i=G.nex[i]){
v=G.to[i];
if(deep[v]!=deep[u]+1||!G.w[i]) continue;
int k=dfs(v,std::min(res,G.w[i]));
if(!k) deep[v]=0;
else G.w[i]-=k,G.w[i^1]+=k,res-=k;
if(!res) break;
}
return now-res;
}
inline void init(){
for(int i=2;i<=G.tot;i+=2){
G.w[i]+=G.w[i^1];
G.w[i^1]=0;
}
}
inline int dinic(int s,int t){
init();S=s;T=t;
int ans=0,now=0;
while(bfs()){
std::memcpy(G.fir_,G.fir,sizeof G.fir);
while(now=dfs(s)) ans+=now;
}
return ans;
}
}F;
int min[11][N],fa[11][N],deep[N];
int node[N],tmp1[N],tmp2[N];
void build(int l,int r){
if(l==r) return;
int s=node[l],t=node[l+1];
int cut=F.dinic(s,t);
T.add(s,t,cut);T.add(t,s,cut);
int cnt1=0,cnt2=0;
for(int i=l;i<=r;i++){
if(F.deep[node[i]]) tmp1[++cnt1]=node[i];
else tmp2[++cnt2]=node[i];
}
for(int i=l;iHLPP 最大流
int S,T;
int left,right,que[N*100];
int in[N];
int h[N],cnth[N*2];
long long res[N];
inline void bfs(){
std::memset(h,0x3f,sizeof h);h[T]=0;
left=right=0;que[0]=T;in[T]=1;
int u;
while(left<=right){
u=que[left++];in[u]=0;
for(int v,i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(!G.w[i^1]||h[v]<=h[u]+1) continue;
h[v]=h[u]+1;
if(!in[v]) que[++right]=v,in[v]=1;
}
}
}
inline int pqueCmp(const int &a,const int &b){return h[a],int(*)(const int &a,const int &b)>pque(pqueCmp);
inline void push(int u){
for(int v,i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(h[v]+1!=h[u]||!G.w[i]) continue;
long long k=std::min(G.w[i],res[u]);
G.w[i]-=k;G.w[i^1]+=k;
res[u]-=k;res[v]+=k;
if(!in[v]&&v!=T&&v!=S) in[v]=1,pque.push(v);
if(!res[u]) break;
}
}
inline void relabel(int u){
h[u]=INT_INF;
for(int v,i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(G.w[i]) h[u]=std::min(h[u],h[v]+1);
}
}
inline long long hlpp(int s,int t){
S=s;T=t;
bfs();
if(h[S]==INT_INF) return 0;
h[S]=n;
for(int i=1;i<=n;i++)if(h[i]h[u]&&i!=S&&i!=T) h[i]=n+1;
}
relabel(u);cnth[h[u]]++;
pque.push(u);in[u]=1;
}
}
return res[T];
}
Stoer-Wagner 求无向图最小割
int S,T;
int w[N],inA[N];
int del[N],dis[N][N];
inline int mincut(int x){
std::memset(w,0,sizeof w);std::memset(inA,0,sizeof inA);
w[0]=-1;
for(int id,i=1;i<=n-x+1;i++){
id=0;
for(int j=1;j<=n;j++)if(!inA[j]&&!del[j]&&w[j]>w[id]) id=j;
inA[id]=1;
if(i==n-x) S=id;
else if(i==n-x+1) T=id;
for(int j=1;j<=n;j++)if(!inA[j]&&!del[j]) w[j]+=dis[id][j];
}
return w[T];
}
inline int sw(){
int ret=1e9;
for(int i=1;itarjan 最小树形图
int uniFa[N];
inline int find(int k){return k==uniFa[k]?k:uniFa[k]=find(uniFa[k]);}
struct Edge{
int u,v,w,w0;
};
struct Node{
Node *ls,*rs,*root;
int deep,tag;
Edge *edge;
inline void pushdown(){
ls->tag+=tag;rs->tag+=tag;
edge->w+=tag;
tag=0;
}
}nullNode,*null=&nullNode;
int tot;
inline void New(Node *&x,Edge *e){
x=new Node;
x->deep=1;x->tag=0;
x->ls=x->rs=null;
x->root=x;x->edge=e;
}
Node *merge(Node *x,Node *y){
if(x==null) return y;
if(y==null) return x;
if(x->edge->w+x->tag>y->edge->w+y->tag) std::swap(x,y);
x->pushdown();
x->rs=merge(x->rs,y);
if(x->ls->deeprs->deep) std::swap(x->ls,x->rs);
x->deep=x->rs->deep+1;
x->ls->root=x->rs->root=x;
return x;
}
inline void pop(Node *&x){
x->pushdown();
Node *ls=x->ls,*rs=x->rs;
delete x;
x=merge(ls,rs);
}
int n,m;
int vis[N],fa[N];
int nex[N];
Edge *in[M],edge[M];
Node *p[N];
inline void contraction(){
for(int i=1;i<=n;i++) p[i]=null,uniFa[i]=i;
for(int i=1;i<=m;i++){
Node *tmp;
New(tmp,&edge[i]);
p[edge[i].v]=merge(p[edge[i].v],tmp);
}
vis[1]=1;
for(int u=1,pre=1,o;p[u];pre=u,vis[u]=1){
do{
in[u]=p[u]->edge;pop(p[u]);
u=find(in[u]->u);
}while(u==pre&&p[u]!=null);
if(u==pre) break;
if(!vis[u]) continue;
p[++n]=null;uniFa[n]=n;
for(pre=u;u^n;){
uniFa[u]=fa[u]=n;
if(p[u]!=null) p[u]->tag-=in[u]->w;
p[n]=merge(p[n],p[u]);
o=find(in[u]->u);
nex[o==n?pre:o]=u;
u=o;
}
}
}
int expand(int,int);
int expand(int u){
int ans=0;
for(int x=nex[u];x^u;x=nex[x]){
if(in[x]->w0==INT_INF) return INT_INF;
if((ans+=in[x]->w0+expand(in[x]->v,x))>=INT_INF) return INT_INF;
}
return ans;
}
inline int expand(int u,int goal){
int ans=0;
for(;u^goal;u=fa[u])
if((ans+=expand(u))>=INT_INF) return INT_INF;
return ans;
}
int main(){
n=read();m=read();int root=read();
for(int i=1;i<=m;i++) edge[i].u=read(),edge[i].v=read(),edge[i].w=edge[i].w0=read();
for(int i=1;i spfa 找负环
int dis[N],cnt[N];
int left,right,que[N];
inline int spfa(){
std::memset(dis,0x3f,sizeof dis);std::memset(cnt,0,sizeof cnt);
right=left=0;que[0]=1;
dis[1]=0;
int u,v,i;
while(left<=right){
u=que[left++];
for(i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(dis[v]>dis[u]+G.w[i]){
dis[v]=dis[u]+G.w[i];
cnt[v]++;
if(cnt[v]>n) return 1;
que[++right]=v;
}
}
}
return 0;
}
支配树
Graph G,H,T;
int uni[N],min[N];
int dfscnt,dfn[N],id[N],fa[N];
int sdom[N],idom[N];
inline int find(int k){
if(k==uni[k]) return k;
int ret=find(uni[k]);
if(dfn[sdom[min[uni[k]]]]1;i--){
u=id[i];
for(int v,i=H.fir[u];i;i=H.nex[i]){
v=H.to[i];
if(!dfn[v]) continue;
find(v);
if(dfn[sdom[min[v]]]1;i--) ans[idom[id[i]]]+=++ans[id[i]];
ans[id[1]]++;
}
LGV 引理
https://oi-wiki.org//graph/lgv/
匈牙利
int match[N],vis[N];
int dfs(int u){
for(int v,i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(vis[v]) continue;
vis[v]=1;
if(!match[v]||dfs(match[v])) return match[v]=u,match[u]=v,1;
}
return 0;
}
二分图最大权匹配 KM
int num_left,num_right;
int G[N][N];
int vis[N],pre[N],match[N],lw[N],d[N];
int que[N],tail,head;
inline int bfs(int u){
tail=head=0;que[0]=u;
pre[u]=0;
while(tail<=head){
u=que[tail++];vis[u]=1;
for(int i=num_left+1;i<=num_right;i++)if(G[u][i]==lw[u]+lw[i]){
if(vis[i]) continue;
vis[i]=1;
if(match[i]) pre[match[i]]=u,que[++head]=match[i];
else{
int d=u,e=i,t;
while(d){
t=match[d];
match[d]=e;match[e]=d;
d=pre[d];e=t;
}
return 1;
}
}
}
return 0;
}
inline LL max_match(){
for(int i=1;i<=num_left;i++){
for(int j=num_left+1;j<=num_right;j++) lw[i]=std::max(lw[i],G[i][j]);
}
for(int i=1;i<=num_left;i++){
std::memset(vis,0,sizeof vis);std::memset(d,0x3f,sizeof d);
if(bfs(i)) continue;
for(int j=1;j<=num_left;j++)if(vis[j])
for(int k=num_left+1;k<=num_right;k++)
if(!vis[k]) d[k]=std::min(d[k],lw[j]+lw[k]-G[j][k]);
while(1){
int now=INT_INF,to,s;
for(int j=num_left+1;j<=num_right;j++)if(!vis[j]) now=std::min(now,d[j]);
for(int j=1;j<=num_left;j++)if(vis[j]) lw[j]-=now;
for(int j=num_left+1;j<=num_right;j++)
if(vis[j]) lw[j]+=now;
else d[j]-=now,to=d[j]?to:j;
if(!match[to]) break;
s=match[to];vis[to]=vis[s]=1;//打上 vis 标记
for(int j=num_left+1;j<=num_right;j++)if(!vis[j]) d[j]=std::min(d[j],lw[s]+lw[j]-G[s][j]);
}
std::memset(vis,0,sizeof vis);
bfs(i);
}
long long ans=0;
for(int i=1;i<=num_right;i++) ans+=lw[i];
return ans;
}
建虚树
inline void buildVT(int n,int *a,Graph &G){
std::sort(a+1,a+1+n,[](const int &p,const int &q){return dfn[p]树的最小表示法
struct Center{int a,b;};
int size[N],maxson[N];
void getMaxs(int u,int fa,int n,const Graph &G){
size[u]=1;maxson[u]=0;
for(int v,i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(v==fa) continue;
getMaxs(v,u,n,G);
size[u]+=size[v];maxson[u]=std::max(maxson[u],size[v]);
}
maxson[u]=std::max(maxson[u],n-size[u]);
}
inline Center getCenter(int n,const Graph &G){
getMaxs(1,0,n,G);
int min=1e9;
for(int i=1;i<=n;i++) min=std::min(maxson[i],min);
Center ret={0,0};
for(int i=1;i<=n;i++)if(maxson[i]==min) (ret.a?ret.b:ret.a)=i;
return ret;
}
int fa[N];
std::vectorp[N];
int dfs(int u,int deep,const Graph &G){
p[deep].push_back(u);
int ret=deep;
for(int v,i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(v==fa[u]) continue;
fa[v]=u;
ret=std::max(ret,dfs(v,deep+1,G));
}
return ret;
}
int tag[N];
std::vectorsonTag[N];
inline void getans(int u,int *ans,const Graph &G){
ans[++ans[0]]=0;
std::vectorv;
for(int i=G.fir[u];i;i=G.nex[i])if(G.to[i]^fa[u]) v.push_back(G.to[i]);
std::sort(v.begin(),v.end(),[](const int &a,const int &b){return tag[a] 点分治
int root,sum;
void find(int x,int fa=0){
size[x]=1;max[x]=0;
for(int v,i=G.fir[x];i;i=G.nex[i]){
v=G.to[i];
if(v==fa||vis[v]) continue;
find(v,x);
size[x]+=size[v];
if(max[x]