最短路
DJ
void Dj(int st) { memset(dis,0x3f,sizeof(dis)); pa tmp=make_pair(0,st); q.push(tmp); dis[st]=0; while(!q.empty()) { int x=q.top().second; q.pop(); if(v[x])continue; v[x]=1; for(int i=head[x];i;i=nxt[i]) { if(dis[to[i]]>dis[x]+len[i]) { dis[to[i]]=dis[x]+len[i]; q.push(make_pair(-dis[to[i]],to[i])); } } } }
spfa
void spfa(int s,int t) { memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); int l=0,r=0; dis[1]=0;q[r++]=1; while(l<r) { int x; vis[x=q[l++]]=0; for(int i=head[x];i;i=nxt[i]) { if(dis[to[i]]>dis[x]+len[i]) { dis[to[i]]=dis[x]+len[i]; if(!vis[to[i]]) vis[q[r++]=to[i]]=1; } } } }
拓扑排序
bool topsort() { for(int i=1;i<=n;i++) if(!deg[i])q.push(i); while(!q.empty()) { int u=q.top(); ans.push_back(u); q.pop(); for(int i=head[u];i;i=nxt[i]) if(!(--deg[to[i]]))q.push(to[i]); } if(ans.size()!=n)return false; return true; }
最小生成树（Kruskal）
for(int i=1;i<=n;i++)fa[i]=i; ans=0; int t=0; for(int i=1;i<=m;i++) { int x=e[i].s,y=e[i].t; int fx=findf(x),fy=findf(y); if(fx!=fy) { fa[fx]=fy; ans+=e[i].l; t++; } if(t==n-1)break; }
求LCA
倍增
void dfs(int x,int deep) { dep[x]=deep; for(int i=1;i<=20;i++) fa[x][i]=fa[fa[x][i-1]][i-1]; for(int i=head[x];i;i=nxt[i]) { if(dep[to[i]])continue; fa[to[i]][0]=x; dfs(to[i],deep+1); } } int LCA(int x,int y) { if(dep[x]>dep[y])swap(x,y); for(int i=20;i>=0;i--) if(dep[fa[y][i]]>=dep[x])y=fa[y][i]; if(x==y)return x; for(int i=20;i>=0;i--) if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; return fa[x][0]; }
匈牙利算法
bool find(int x) { for(int y=1;y<=n;y++) if(map[x][y]&&!vis[y]) { vis[y]=1; if(!match[y]||find(match[y])) { match[y]=x; return true; } } return false; }
线段树优化建图
(a,b)->(c,d)
#include<cstdio> #include<iostream> #include<cstring> #include<queue> using namespace std; #define pa pair<int,int> const int N=500005,M=3000005; int n,m,to[M<<3],nxt[M<<3],len[M<<3],head[M],tot,dis[M],s,v[M]; int ls[N<<2],rs[N<<2],type,key[N<<2],root1,root2; priority_queue<pa> q; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } void add(int x,int y,int z) { to[++tot]=y; len[tot]=z; nxt[tot]=head[x]; head[x]=tot; } void build(int &k,int l,int r,int val) { k=++type; if(l==r) { if(val)key[l]=k; return ; } int mid=l+r>>1; build(ls[k],l,mid,val); build(rs[k],mid+1,r,val); if(val)add(ls[k],k,0),add(rs[k],k,0); else add(k,ls[k],0),add(k,rs[k],0); } void pre(int l,int r,int x,int y) { if(l==r) { add(y,x,0); return ; } int mid=l+r>>1; pre(l,mid,ls[x],ls[y]); pre(mid+1,r,rs[x],rs[y]); } void update(int S,int T,int l,int r,int x,int y,int val) { if(S<=l&&r<=T) { if(val)add(x,y,0); else add(y,x,0); return ; } int mid=l+r>>1; if(S<=mid)update(S,T,l,mid,ls[x],y,val); if(T>mid)update(S,T,mid+1,r,rs[x],y,val); } void link(int a,int b,int c,int d) { update(a,b,1,n,root1,++type,1); add(type,type+1,1); update(c,d,1,n,root2,++type,0); } void Dj(int st) { memset(dis,0x3f,sizeof(dis)); pa tmp=make_pair(0,key[st]); q.push(tmp); dis[key[st]]=0; while(!q.empty()) { int x=q.top().second; q.pop(); if(v[x])continue; v[x]=1; for(int i=head[x];i;i=nxt[i]) { if(dis[to[i]]>dis[x]+len[i]) { dis[to[i]]=dis[x]+len[i]; q.push(make_pair(-dis[to[i]],to[i])); } } } } int main() { n=read();m=read();s=read(); build(root1,1,n,1);build(root2,1,n,0); pre(1,n,root1,root2); for(int i=1;i<=m;i++) { int a=read(),b=read(),c=read(),d=read(); link(a,b,c,d);link(c,d,a,b); } Dj(s); for(int i=1;i<=n;i++) printf("%d ",dis[key[i]]); return 0; }
Tarjan
缩点（有向图）
void tarjan(int x) { dfn[x]=low[x]=++ind; vis[x]=1; st[++top]=x; for(int i=0;i<g[x].size();i++) { int y=g[x][i]; if(!dfn[y]) { tarjan(y); low[x]=min(low[x],low[y]); } else if(vis[y])low[x]=min(dfn[y],low[x]); } if(dfn[x]==low[x]) { scc++; int now=0; do { now=st[top--]; vis[now]=0; bel[now]=scc; } while(now!=x); } }
求割点（无向图）
int dfn[MAXN],low[MAXN],cnt,root; bool iscut[MAXN]; void tarjan(int x) { dfn[x]=low[x]=++cnt; int flag=0; for(int i=head[x];i;i=nxt[i]) if(!dfn[to[i]]) { tarjan(to[i]),low[x]=min(low[x],low[to[i]]); if(low[to[i]]>=dfn[x]) { flag++; if(x!=root || flag>1)iscut[x]=1; } } else low[x]=min(low[x],dfn[to[i]]); } for(int i=1;i<=n;i++) if(!dfn[i]){root=i;tarjan(i);}
求桥
void tarjan(int x,int f)
{
low[x]=dfn[x]=++ind;
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==f)continue;
if(!dfn[y])
{
tarjan(y,x);
low[x]=min(low[x],low[y]);
if(low[y]>dfn[x])isbr[i]=isbr[i^1]=1,ans++;
}
else if(y!=f)low[x]=min(low[x],dfn[y]);
}
}
非递归求欧拉路
int syst[N*10],systop;
void euler()
{
systop=0;
syst[++systop]=0;
while(systop>0)
{
int x=syst[systop],i=head[x];
while(i&&v[i])i=nxt[i];
if(i)
{
syst[++systop]=to[i];
v[i]=v[i^1]=1;
head[x]=nxt[i];
}
else systop--,st[++top]=x;
}
}