一.单源最短路

常用算法

练习题及做法

1. ①热浪②信使
   经典最短路
2. 香甜的黄油
   枚举起点+最短路
3. 最小花费
   转化最短路
   转化条件：①乘法运算->加法运算可以通过取$log$实现，由于此题目中$0< w\leq1$因此取 $log$ 后边权恒为负数稍作转化可用$dijkstra算法$。倘若题目只有$w>0$只能用$SPFA$
4. 最优乘车
   stringstream方便建图
5. 昂贵的聘礼
   虚拟源点+枚举
   交易方式：①直接购买②在一个物品的基础上+交易费。虚拟源点向各个物品连一条边，权值表示直接购买费用，然后物品之间的交易费为其他边权值。等级限制直接枚举区间即可
6. 新年好
   预处理+$dfs$
   预处理出佳佳及所有亲戚家为起点的最短路，然后暴力枚举方案求最短路
7. 通信线路
   二分+最短路
   转化题目需求$1$~$n$的所有路径第$k+1$大的值最小即最大值最小模型。
   二分答案，check(mid)函数中求从$1$~$n$中，最少经过长度大于$mid$的边数是否小于等于$k$
8. 道路与航线
   $dijkstra$+DAG
   在DAG图中，可以通过递推的方式求得最短路，由于道路之间无负权边，因而可在道路连通块内用$dijkstra$求最短路，把道路看出一堆连通块，然后通过航线链接，题目分析可知由航线链接的方式为DAG图，因而可以递推求出最终问题
9. 最优贸易
   动规思想+最短路
   集合角度考虑：每个城市都可能作为买卖的中间的，因此可枚举买卖中间点$i$，求出$1$~$i$中买入水晶球的最低价格dmin[i]和从$i$~$n$的过程中，卖出水晶球的最高价格dmax[i]，求出dmax[i]-dmin[i]的最大值
   注意：①为保证卖出地点最终能够到达目的地求从$i$~$n$的过程中，卖出水晶球的最高价格dmax[i]，需要反向建边求②求一条路径上边的最大值/最小值只能用$SPFA$不能用$dijkstra$
10. ①最短路计数②观光
    方案个数+次短路
    ②维护最短路+最短路方案+次短路+次短路方案
11. ①拯救大兵瑞恩 ②装满的油箱
    动规思想+建图+拆点
    ①目前状态决定方式：<1>位置<2>手中钥匙
    ②目前状态决定方式：<1>位置<2>油量
    倘若确定状态不仅仅需要位置，而且还有其他状态考虑拆点
12. 选择最佳线路
    虚拟源点
    多起点单终点可考虑反向建图，多起点多终点考虑虚拟源点

二.floyd算法变形

解决问题

① 牛的旅行——多源最短路
② 排序 ——传递闭包
③ 观光之旅 ——最小环
④ 牛站 ——恰好经过k条边的最短路

代码

传递闭包模板

void floyd()
{
    for (int k = 0; k < n; k ++ )
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < n; j ++ )
                d[i][j] |= d[i][k] && d[k][j];
}

牛站$Bellman-ford$

/*
保证每次迭代k都会更新很直接的想法是直接赋值
dist[a]=backup[b]+w;
dist[b]=backup[a]+w;
像上面，但是这是不对的，因为在一次迭代过程中可能多次更新dist[a]，我们需要的是路径最小的dist[a]
*/
void bellman_ford()
{
    memset(dist,0x3f,sizeof dist);
    dist[S]=0;
    for(int i=0;i<k;i++)
    {
        memcpy(backup,dist,sizeof dist);//表示经过只i条边
        memset(dist,0x3f,sizeof dist);//保证每次迭代k都会更新一条边而且更新的一条边是最小的
        for(int j=0;j<m;j++)
        {
            int a=e[j].a,b=e[j].b,w=e[j].w;
            dist[a]=min(dist[a],backup[b]+w);//无向图两条边
            dist[b]=min(dist[b],backup[a]+w);
        }
    }
}

三.最小生成树

常用算法

kruskal算法求最小生成树的同时会维护很多额外的信息相对prim算法更加灵活也更加常用

练习题分析

1. 最短网络 典型最小生成树
2. 局域网
   最小生成森林，$kruskal$可以直接求而$prim$可能要费点劲 prim做法
3. ①繁忙的都市 ②联络员 ③连接格点
   这三题用$kruskal$非常好求，而$prim$十分费劲，甚至求不了
4. 新的开始
   超级源点+最小生成树
   假想一个超级供电站向每个点连一条边，然后求最小生成树
5. 北极通讯网络
   $kruskal$+连通块
   对于$kruskal$算法即用每次用当前最小边连接两个连通块，每次添加一条边连通块数量就会减小1
6. 走廊泼水节
   $kruskal$维护额外信息
   秦大佬题解
7. 秘密的牛奶运输
   次小生成树
   次小生成树求法：

方法1：次小生成树可由替换最小生成树的一条边(u,v)得到，显然这条边肯定不可能属于原最小生成树，如果我们将一条不属于原最小生成树的边(u,v)加入T，那么此时T中就形成了一个环，我们在环中选一个除(u,v)权值最大的边进行删除，得到的树依然是一颗图G的生成树，我们将所有边逐个加入原最小生成树T，得出并记录所有的生成树的权值T1，那么最后T1中最小的那个值即是次小生成树的权值

方法2：依次枚举最小生成树中的树边，在不用该边的情况下在剩余边再求最小生成树
通常使用第一种方法求次小生成树，倍增可以优化求次小生成树

四.$SPFA$进阶用法

4.1.1负环

通常用cnt[i]表示i这个节点的进队次数即被更新次数，一旦存在一个节点更新次数超过或者等于节点总数那么存在负环.如果$spfa$更新次数较多我们通常也认为存在负环（玄学$SPFA$）

4.1.2练习题及分析

1. 虫洞
   阅读理解+负环
2. 单词环
   栈优化
   通常用$SPFA$求最短路我们用队列存储节点，而对于求负环用栈效果会更好
   注意：最短路用队列，求负环用栈
3. 观光奶牛
   01分数规划+负环
   对于01分数规划问题，通常使用二分求解，对于最短路上的01分数规划，其实是转化边权求正环

4.2.1差分约束

差分约束问题如果利用图论中的三角不等式那么就可以进行完美转化。详细请看 二助佐助分享
最小值->最长路
最大值->最短路
对于一组不等式通常只能求出相对关系，倘若需求最值那么一定可以挖掘一些信息使得某个点的值被限制。
源点需要能遍历图中所有的边即最终所求需满足全部差分约束的不等关系
注意：①边权无限制->SPFA糖果 ②边权非负->tarjan 银河 ③边权为正数->拓扑排序 奖金

4.2.2练习题及分析

1. 糖果
   线性约束
2. 区间 排队布局
   区间约束
   对于区间约束我们通常使用前缀和将其转化成线性约束
3. 雇佣收银员
   不确定约束
   求最值必须有一个点被限制，但此题并没有，不过我们可以通过枚举约束条件来限制一个点

五.最近公共组先

代码模板

void dfs(int root)//dfs预处理fa[j][k]表示从j节点向上跳2^k步的节点和depth[j]数组
{
    for(int i=h[root];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(depth[j]>depth[root]+1)
        {
            depth[j]=depth[root]+1;
            fa[j][0]=root;
            for(int k=1;k<=15;k++)
                fa[j][k]=fa[fa[j][k-1]][k-1];
            dfs(j);
        }
    }
}
void bfs(int root)//bfs预处理fa[j][k]表示从j节点向上跳2^k步的节点和depth[j]数组
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0;//哨兵
    depth[root]=1;
    queue<int> q;
    q.push(root);
    while(q.size())
    {
        int t=q.front();q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(depth[j]>depth[t]+1)
            {
                depth[j]=depth[t]+1;
                q.push(j);
                fa[j][0]=t;
                for(int k=1;k<=15;k++)
                    fa[j][k]=fa[fa[j][k-1]][k-1];
            }
        }
    }
}

由于$dfs$可能爆栈，通常情况下我们用$bfs$进行预处理

//lca步骤 ①首先将a节点跳到与b节点同层②两个点一起跳跳到公共祖先下一层那么再跳一层即为最近公共祖先f[a][0]
int lca(int a,int b)
{
    if(depth[a]<depth[b]) swap(a,b);
    for(int k=15;k>=0;k--)
        if(depth[fa[a][k]]>=depth[b])
            a=fa[a][k];
    if(a==b) return a;
    for(int k=15;k>=0;k--)
        if(fa[a][k]!=fa[b][k])//跳到公共组先的下一层，跳出根节点那么fa[a][k]=0;
        {
            a=fa[a][k];
            b=fa[b][k];
        }
    return fa[a][0];
}

练习题及分析

1. 祖孙询问
   LCA
2. 次小生成树
   倍增优化最小生成树
3. 闇の連鎖
   LCA+树上差分
   秦大佬题解
4. 距离
   tarjan离线算法求LCA

Tarjan – 离线求LCA
在线做法：读一个询问，处理一个，输出一个
离线做法：读完全部询问，再全部处理完，再全部输出
Tarjon本质就是对向上标记法的一个优化，任取一个节点当成根节点进行dfs优先遍历，在深度优先遍历时，将所有点分成三大类

• 已访问并回溯的节点标记成2
• 已访问但未回溯的节点标记成1
• 还未访问的节点标记成0
  用已经访问并且回溯的节点更新答案

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
const int N=10010,M=N*2;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
int p[N],st[N],dist[N];
vector<PII> query[N];
int res[M];
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int u,int fa)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        dist[j]=dist[u]+w[i];
        dfs(j,u);
    }
}
int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
/*为什么先遍历子树再合并节点？
比如在正在遍历的一条路径上a->b->c->d刚刚遍历完c节点的子树并回溯到c节点
那么假如有一个询问是在 c-d 节点之间 对于d节点st[d]=2;
如果先p[j]=u,p[a]=a,p[b]=a,p[c]=b那么在进行anc=find(d)操作时会把d的祖先p[d]直接路径压缩成a节点
如果后p[j]=u,p[a]=a,p[b]=b,p[c]=c那么在进行anc=find(d)操作时找到p[d]=c
显然我们要找最近公共祖先,必须先遍历再合并
*/
void tarjan(int u)
{
    st[u]=1;//遍历但未回溯
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            tarjan(j);//遍历子树
            p[j]=u;//合并节点
        }
    }
    for(auto t:query[u])
    {
        int y=t.first,id=t.second;
        if(st[y]==2)
        {
            int anc=find(y);
            res[id]=dist[u]+dist[y]-dist[anc]*2;
        }
    }
    st[u]=2;//结束回溯
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    for(int i =0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        if(a!=b)
        {
            //a,b之中肯有有一个点先遍历完并已经回溯,我们只有在已经回溯的时候才进行更新答案
            query[a].push_back({b,i});
            query[b].push_back({a,i});
        }
    }
    for(int i=1;i<=n;i++) p[i]=i;
    dfs(1,-1);
    tarjan(1);
    for(int i=0;i<m;i++) cout<<res[i]<<endl;
    return 0;
}

欧拉序+ST表求lca
参考文章

// acwing 1172
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=40010;
int h[N],e[2*N],ne[2*N],idx;
int n,q;
int eular[N*10],cnt,dfn[N];
int ST[N*5][18];
int lg[N*5],dep[N];
void dfs(int u,int fa)
{
    dfn[u]=++cnt;
    eular[cnt]=u;
    dep[u]=dep[fa]+1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        dfs(j,u);
        eular[++cnt]=u;
    }
}
void pre()
{
    lg[1]=0;
    for(int i=2;i<=cnt;i++) lg[i]=lg[i>>1]+1;
    for(int i=1;i<=cnt;i++) ST[i][0]=eular[i];
    for(int j=1;j<=lg[cnt];j++)
        for(int i=1;i+(1<<j)-1<=cnt;i++)
        {
            if(dep[ST[i][j-1]]<dep[ST[i+(1<<j-1)][j-1]]) ST[i][j]=ST[i][j-1];
            else ST[i][j]=ST[i+(1<<j-1)][j-1];
        }
}
int lca(int a,int b)
{
    a=dfn[a],b=dfn[b];
    if(a>b) swap(a,b);
    int len=lg[b-a+1];
    return dep[ST[a][len]]<dep[ST[b-(1<<len)+1][len]]?ST[a][len]:ST[b-(1<<len)+1][len];
}
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n;
    int root;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        if(b==-1) root=a;
        else add(a,b),add(b,a);
    }
    dfs(root,0);
    pre();
    cin>>q;
    while(q--)
    {
        int a,b;
        cin>>a>>b;
        int pab=lca(a,b);
        if(a==pab) cout<<"1\n";
        else if(b==pab) cout<<"2\n";
        else cout<<"0\n";
    }
    return 0;
}

六.有向图强连通分量

代码模板

belong[i]记录i节点是否在栈中
dfn[i]表示dfs序遍历到i节点的时间戳
low[i]表示从i节点为根的子树中的某个节点j出发只经过一条C边（横向边）或者B（后向边）边能到达节点最小时间戳并且j存在一条路径 j->...->i（等价于j在栈中）
d[i]表示i结点属于哪个强连通分量，scnt表示强连通分量个数，sz[i]表示表示编号为i的强连通分量点的个数

stack<int>stk;
int dfn[N],low[N],timestamp;
bool belong[N];
int id[N],scnt,sz[N];
int dout[N];
void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk.push(u),belong[u]=1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])//T边 祖先->孩子
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(belong[j]) low[u]=min(low[u],dfn[j]);//B边 孩子->祖先 或者 C边横向边
        else continue;//C边 横向边 该边不能走到该点
    }
    if(dfn[u]==low[u])
    {
        scnt++;
        int y;
        do{
            y=stk.top();stk.pop();
            belong[y]=0;
            id[y]=scnt;
            sz[scnt]++;
        }while(y!=u);
    }
}

SOLORED大佬的对Tarjan算法证明 这个证明思路非常清晰，逻辑十分严谨，强烈推荐！！！
补充：$tarjan$算法求完后，对于id[]逆序就是拓扑图，因而不需要拓扑排序

练习题及分析

1. 受欢迎的牛
   $tarjan$缩点+DAG
   发现如果是DAG图，若DAG图只有一个出度未0的连通块，那么该连通块点的数目就是答案，若有多个出度未0的连通块那么分析可知答案为0.$tarjan$算法缩点可将有向图转化成DAG图
2. 学校网络
   $tarjan$缩点+DAG
   想要通过加边的方式将整个有向图变成连通图至少要加max(q,p)条边，p为缩点后入度为0的连通块的数量，q为缩点后出度为0的连通块的数量。 番茄酱大佬给出的证明
3. 最大半连通子图
   $tarjan$缩点+DAG最长路径

   Tarjan 缩点，整个强连通分量选上一定更优。缩点后的DAG图中，如果要求一个最大半连通子图，一定是求一条最长链，以及维护最长连的方案数

4. 银河
   $tarjan$+差分约束
   差分约束问题及转化后求最短路径，对于DAG图最短路径只需要递推即可求出，而判断是否满足约束条件只需要求是否有正环或者负环，对于$tarjan$缩点后的强连通块如果存在两个节点之间边权不为0那么一定存在正环或者负环

图论的题型多变，并且有很多常用技巧，以上对acwing部分图论题目关键点记录下来，方便以后复习使用，要加油哦！