最短路

SPFA

void spfa(int start){
    queue<int>q;
    memset(dis,0x3f,sizeof(dis));
    memset(cis,0x3f,sizeof(cis));
    dis[start]=0;
    q.push(start);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];~i;i=e[i].next){
            int y=e[i].y;
            int w=e[i].w;
            if(dis[y]>dis[x]+w){
                dis[y]=dis[x]+w;
                if(!vis[y]){
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
    return ;
}

dij

struct edge{
    int x,w;
    bool operator <(const edge &s)const{
        return w > s.w;
    }
};

void dij(int start){
    memset(dis,0x3f,sizeof(dis));
    priority_queue<edge>q;
    dis[start]=0;
    q.push(edge{start,dis[start]});
    while(!q.empty()){
        int x=q.top().x;
        q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int i=head[x];~i;i=e[i].next){
            int y=e[i].y;
            int w=e[i].w;
            if(dis[y]>dis[x]+w){
                dis[y]=dis[x]+w;
                q.push(edge{y,dis[y]});
            }
        }
    }
    return ;
}

LCA

倍增

问题：输入一棵n个结点的树，以及m组请求，每个请求是两个结点，求它们的最小公共祖先。

实现思路：先建树，求出每一个点的深度，再根据深度来求lca。

具体实现：

建树求深度，并求出每个点的父节点，方便后面进行跳点、

接下来考虑如何查找最近公共祖先，可以先将两个点升到同一高度，再同时往上跳，但这么做的时间复杂度为O(nm)肯定会超时。这里我用ST表进行优化。

优化思路：下面是一个树，如果我们要求6号节点和7号节点lca，我们可以先列出一个式子，表示第i层时他们的祖先节点是否是同一个点。

如图列出式子如下：F F F T T T

可以看出当第一次达到T时，该点为两点的最近公共祖先。

那我们用ST表记录st[x][i]表示向上跳2^i个点,跳了之后如果该点为两点的祖先节点就换更小的i来跳，反之则将x,y更替为st[x][i],st[y][i]。通过这种方式来进行提速，单次lca的时间复杂度为O(logn),总体时间复杂度为O(mlogn)。

//st表初始化
void init(){
  for(int i=1;i<=n;i++)st[i][0]=fa[i];
  for(int j=1;(1<<j)<=n;j++){
    for(int i=1;i<=n;i++)st[i][j]=st[st[i][j-1]][j-1];
  }
}

//lca模版
int lca(int x,int y){
  if(deep[x]<deep[y]){
    int tp=x;x=y;y=tp;
  }int t=deep[x]-deep[y],i=0;
  while(t){
    if(t%2==1)x=st[x][i];
    t=t>>1;i++;
  }if(x==y)return x;
  for(int i=logn;i>=0;i--){
    if(st[x][i]==st[y][i])continue;
    x=st[x][i];y=st[y][i];
  }return st[x][0];
}

最后完整代码如下：

#include<cstdio>
#include<cmath>
using namespace std;
const int N=1e6+100;

struct node{
	int y,nx;
}e[N];
int n,m,last,logn;
int head[N];
int fa[N];
int deep[N];
int st[N][30];

void add(int x,int y){
	last++;
	e[last].y=y;
	e[last].nx=head[x];
	head[x]=last;
	return ;
}

void dfs(int x,int _fa){
	fa[x]=_fa;
	deep[x]=deep[_fa]+1;
	for(int i=head[x];i;i=e[i].nx){
		int y=e[i].y;
		if(y==_fa)continue;
		dfs(y,x);
	}
	return ;
}

void init(){
	for(int i=1;i<=n;i++)st[i][0]=fa[i];
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i<=n;i++)st[i][j]=st[st[i][j-1]][j-1];
	return ;
}

int lca(int x,int y){
	if(deep[x]<deep[y]){
		int tp=x;
		x=y;
		y=tp;
	}
	int t=deep[x]-deep[y],i=0;
	while(t){
		if(t%2==1)x=st[x][i];
		t=t>>1;i++;
	}
	if(x==y)return x;
	for(int i=logn;i>=0;i--){
		if(st[x][i]==st[y][i])continue;
		x=st[x][i];y=st[y][i];
	}
	return st[x][0];
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	dfs(1,0);
	init();
	logn=log2(n);
	for(int i=1;i<=m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		printf("%d\n",lca(a,b));
	}
	return 0;
}

树链剖分

1.若x所在的重链的链头不等于y所在的重链的链头，表明x和y不在同一条重链上

2.记x和y两点中链头的深度较深的那个点为z

3.将z调到他的链头的father

4.重复以上步骤，知道x与y的链头相等（即在同一条重链上）

5.此时x和y中深度较小的那个点即为LCA

/*
g++ -o2 slpf.cpp -o c -std=c++14
.\c

*/

#include<cstdio>

using namespace std;
typedef long long ll;
const int N=5e6+100;
int tot;
int head[N];
struct node{
    int y,next;
}e[N];

int fa[N];
int dep[N];
int son[N];
int siz[N];
int dfn[N];
int top[N];

int n,m,s;

void swap(int &x,int &y){
    int t=x;
    x=y;
    y=t;
    return ;
}

void add(int x,int y){
    tot++;
    e[tot].y=y;
    e[tot].next=head[x];
    head[x]=tot;
    return ;
}

void dfs_f(int x,int _fa){
    /*
    第一次跑DFS,将每个点的父节点，深度，子节点个数算出来
    并计算出每个点的最大的子节点，当作重儿子
    */
    fa[x]=_fa;
    siz[x]=1;
    dep[x]=dep[_fa]+1;
    int son_max=0;
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].y;
        if(y==_fa)continue;
        dfs_f(y,x);
        siz[x]+=siz[y];
        if(siz[y]>son_max){
            son[x]=y;
            son_max=siz[y];
        }
    }
    return ;
}

void dfs_s(int x,int fa_top){
    /*
    第二次跑DFS，按照上一次跑出来的重儿子优先遍历
    将整个树分成若干条链，并求出每条链的链顶
    */
    top[x]=fa_top;
    if(son[x])dfs_s(son[x],fa_top);
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].y;
        if(y==fa[x])continue;
        if(y==son[x])continue;
        dfs_s(y,y);
    }
    return ;
}

int lca(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}

int main(){
    scanf("%lld%lld%lld",&n,&m,&s);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%lld%lld",&x,&y);
        add(x,y);
        add(y,x);
    }
    // printf("a\n");
    dfs_f(s,0);
    // printf("s\n");
    dfs_s(s,s);
    // printf("d\n");
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%lld%lld",&x,&y);
        printf("%lld\n",lca(x,y));
    }
    return 0;
}

————————————————

联通分量

强联通分量（tarjan）

有向图的极大强连通子图称为的强连通分量，强连通图只有一个强连通分量，即是其自身。非强连通的有向图有多个强连通分量，这里我介绍一种用tarjan的求强连通分量方法。

实现思路:

首先先建图，然后在遍历的过程中对每个点的访问顺序打上标记。结果如下:

可以看出2->3->6->4为一个强连通分量，那么接下来考虑如何将该连通分量的点值化为一个相同的数。

这里可以建两个数组dfn和low，dfn用来记录该点在遍历时的顺序，low则用来记录该点所在的连通分量的顺序。

那么该如何判断遍历过的点是否在一个连通分量上呢？因为连通分量上的点可以互相到达，又因为是有向图，所以强连通分量要么是一个点要么是一个环。即如果在访问的过程中找到一个访问过的点，就在回溯过程中将路径上点的low全部化为一个可以代表整个连通分量的数字，即访问该连通分量时的第一个访问的数字。

实现代码如下：

void tarjan(int x){
	last++;
	dfn[x]=last;
	low[x]=last;
	vis[x]=1;
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].y;
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}else if(vis[x]==1)
			low[x]=min(low[x],dfn[y]);
	}vis[x]=2;
}

但实际上这个代码是有问题的如果出现连个环共用两个及以上的点的话，后遍历的环就会被分成多个连通分量，如图：

在这个图中7会被划分成一个额外的连通分量而不是和2->3->6->4划为一个整体，为了解决这个问题，在这里我们可以用一个color数组去记录每个点所属的连通分量，通过判断下一个遍历点是否处于同一色块来判断是非需要划分。

在遍历的过程中可以用一个栈来存储已经遍历过的点，在发现low[x]==dfn[x]时将栈里面的点都划上颜色，即到达该连通分量的第一点时进行划分。

void tarjan(int x){
	last++;
    dfn[x]=last;
    low[x]=last;
    stk.push(x);
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].y;
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}else if(color[y]==0)low[x]=min(low[x],dfn[y]);
	}if(dfn[x]==low[x]){//判断是否位于该连通分量第一点
		++cidx;//新增一个颜色
		while(!stk.empty()){
			int t=stk.top();stk.pop();
			color[t]=cidx;//上色
			if(t==x)break;//染色完后退出
		}
	}
}

最后输出每一个连通块遍历完后的颜色总数，完整代码如下：

#include<cstdio>
#include<stack>
using namespace std;
const int N=1e5+100;
int n,m;
struct node{
	int y,next;
}e[N];
stack<int>stk;
int head[N],color[N];
int tot,cidx,last;
int dfn[N],low[N];
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;} 
void add(int x,int y){//存图
	tot++;
	e[tot].y=y;
	e[tot].next=head[x];
	head[x]=tot;
}void tarjan(int x){
	last++;dfn[x]=last;low[x]=last;stk.push(x);
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].y;
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}else if(color[y]==0)low[x]=min(low[x],dfn[y]);
	}if(dfn[x]==low[x]){
		++cidx;
		while(!stk.empty()){
			int t=stk.top();stk.pop();
			color[t]=cidx;
			if(t==x)break;
		}
	}
}int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
	}for(int i=1;i<=n;i++)if(!color[i])tarjan(i);
	printf("%d\n",cidx);
	return 0;
}

边双连通分量

/*
g++ -o2 edge_DCC.cpp -o c -std=c++14
.\c

*/

#include<cstdio>

using namespace std;
const int N=1e5+100;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
int ops(int x){return x^1;}

int head[N];
int tot;

int dfn[N];
int low[N];
int color[N];
int cidx;
int last;
int bridge[N];

struct node{
    int y,next;
}e[N];

void add(int x,int y){
    tot++;
    e[tot].y=y;
    e[tot].next=head[x];
    head[x]=tot;
    return ;
}

void tarjan(int x,int in_edge){
    last++;
    dfn[x]=last;
    low[x]=last;
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].y;
        if(!dfn[y]){
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<low[y]){
                bri[i]=1;
                bri[ops(i)]=1;
            }
        }
        else if(in_edge!=(i^1))low[x]=min(low[x],dfn[y]);
    }
}

void dfs(int x){
    color[x]=cidx;
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].y;
        if(bri[i]||color[y])continue;
        dfs(y);
    }
}

int main(){
}

树链剖分及树上操作

/*
g++ -o2 sp_xds.cpp -o c -std=c++14
.\c

*/ 

#include<cstring>
#include<cstdio>

using namespace std;
typedef long long ll;
const int N=1e6+100;
const int M=1e3+100;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}

int tot;
int head[N];
struct edge{
    int y,w;
    int next;
}e[N];
struct node{
    int l,r;
    int pre;
    int add;
}t[N];

int ls(int p){return p<<1;}
int rs(int p){return p<<1|1;}
int ms(int p){return (t[p].l+t[p].r)>>1;}
int ops(int p){return p^1;}

int dfn[N];
int dep[N];
int siz[N];

int top[N];
int fat[N];
int son[N];
int cod[N];
int last;

int n,m;
int num[N];

void swap(int &x,int &y){
    int t=x;
    x=y;
    y=t;
    return ;
}

void add_edge(int x,int y){
    e[tot].y=y;
    e[tot].next=head[x];
    head[x]=tot++;
    return ;
}

void make_edge(int x,int y){
    add_edge(x,y);
    add_edge(y,x);
    return ;
}

void dfs_fir(int x,int fa){
    dep[x]=dep[fa]+1;
    fat[x]=fa;
    siz[x]=1;
    int son_max=0;
    int son_wei=0;
    for(int i=head[x];~i;i=e[i].next){
        int y=e[i].y;
        if(y==fa)continue;
        dfs_fir(y,x);
        siz[x]+=siz[y];
        if(siz[y]>son_max){
            son_max=siz[y];
            son_wei=y;
        }
    }
    son[x]=son_wei;
    return ;
}

void dfs_sec(int x,int fa_top){
    top[x]=fa_top;
    dfn[x]=++last;
    cod[last]=num[x];
    if(!son[x])return ;
    dfs_sec(son[x],fa_top);
    for(int i=head[x];~i;i=e[i].next){
        int y=e[i].y;
        if(y==fat[x])continue;
        if(y==son[x])continue;
        dfs_sec(y,y);
    }
    return ;
}

void push_up(int p){
    t[p].pre=t[ls(p)].pre+t[rs(p)].pre;
    return ;
}

void push_down(int p){
    if(t[p].add){
        t[ls(p)].pre+=t[p].add*(t[ls(p)].r-t[ls(p)].l+1);
        t[rs(p)].pre+=t[p].add*(t[rs(p)].r-t[rs(p)].l+1);
        t[ls(p)].add+=t[p].add;
        t[rs(p)].add+=t[p].add;
        t[p].add=0;
    }
}

void build(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    if(l==r){
        t[p].pre=cod[l];
        return ;
    }
    int mid=ms(p);
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
    return ;
}

void change_len(int p,int l,int r,int w){
    if(l<=t[p].l && t[p].r<=r){
        t[p].pre+=w*(t[p].r-t[p].l+1);
        t[p].add+=w;
        return ;
    }
    push_down(p);
    int mid=ms(p);
    if(l<=mid)change_len(ls(p),l,r,w);
    if(r> mid)change_len(rs(p),l,r,w);
    push_up(p);
    return ;
}

int ask_len(int p,int l,int r){
    // printf("start : ask_len ( %lld : %lld , %lld )\n",p,l,r);
    if(l<=t[p].l && t[p].r<=r)return t[p].pre;
    push_down(p);
    int mid=ms(p);
    int ans=0;
    if(l<=mid)ans+=ask_len(ls(p),l,r);
    if(r> mid)ans+=ask_len(rs(p),l,r);
    // printf("end : ask_len\n");
    return ans;
}

int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=fat[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}

void change_way(int x,int y,int w){
    if(dep[x]<dep[y])swap(x,y);
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        change_len(1,dfn[top[x]],dfn[x],w);
        x=fat[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    change_len(1,dfn[x],dfn[y],w);
    return ;
}

int ask_way(int x,int y){
    // printf("start : ask_way\n");
    if(dep[x]<dep[y])swap(x,y);
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ans+=ask_len(1,dfn[top[x]],dfn[x]);
        x=fat[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    ans+=ask_len(1,dfn[x],dfn[y]);
    // printf("end : ask_way\n");
    return ans;
}

void change_dot_tree(int x,int w){
    change_len(1,dfn[x],dfn[x]+siz[x]-1,w);
    return ;
}

int ask_dot_tree(int x){
    return ask_len(1,dfn[x],dfn[x]+siz[x]-1);
}

void init(){
    memset(head,-1,sizeof(head));
    return ;
}

void debug_build(){
    printf("\n");
    printf("%lld\n",tot);
    for(int i=0;i<tot;i+=2){
        int x=e[ops(i)].y;
        int y=e[i].y;
        int w=e[i].w;
        printf("%lld -> %lld : %lld\n",x,y,w);
    }
    printf("\n");
    return ;
}

int main(){
    // freopen("w.txt","r",stdin);
    scanf("%lld%lld",&n,&m);
    init();
    for(int i=1;i<=n;i++){
        scanf("%lld",&num[i]);
    }
    
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%lld%lld",&x,&y);
        make_edge(x,y);
    }
    dfs_fir(1,0);
    dfs_sec(1,1);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int x,y,w;
        int op;
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld%lld",&x,&w);
            change_way(x,x,w);
        }
        if(op==2){
            scanf("%lld%lld",&x,&w);
            change_dot_tree(x,w);
        }
        if(op==3){
            scanf("%lld",&x);
            printf("%lld\n",ask_way(1,x));
        }
    }
    return 0;
}

图论模板

最短路