算法集合&总结

Stars_visitor_tyw

2024-06-04 21:16:39

算法·理论

写在最前面

前言

此文章是本人学习算法时的学习笔记。

部分知识点从本人专栏收录。

更新日志

2024 开坑。

线段树 Segment Tree 2024.7
权值线段树 Weighted segment tree 2024.7
树形 DP 2024.7
强连通分量（SCC，Strongly Connected Components） 2024.7
单调队列 2024.7
单调栈 2024.7
Dijkstra 算法 2024.7
Bellman-Ford 算法 2024.7
SPFA 算法 2024.7
换根DP 2024.7
区间DP 2024.8
分块 2024.8
RMQ(Range Maximum/Minimum Query) 2024.8
状态压缩DP 2024.8
LCA（Lowest Common Ancestor） 2024.8
树状数组 2024.8
复习背包 2024.9
IDDFS迭代加深搜索 2024.10
IDA* 启发式迭代加深搜索 2024.10
点双连通&边双连通&割点与割边 2024.11
题目part
线段树 Segment Tree

使用场景
1. 对数列进行区间询问（包括最值、求和、乘积等询问）。

对数列进行区间修改（统一赋值、增减）。

使用思想

分治。

详解

手造一段数列：

2 5 9 1 7 6 5 3

给定 m 次操作：

type1. 将区间 [L,R] 加上 val。

type2. 询问区间[L,R] 的元素和。

下图详解。

位置不够，画的有点混乱了。

每个点上方的红色数字代表 tree_i 的值，蓝色中括号括起来的则为管辖区间。

算法实现

建一棵线段树
查询函数
修改函数

时间复杂度分析

线段树结点编号达到 4\times n。
build O(n)
query O(\log _2^n)
update O(n)（未优化）

未优化代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int a[N],tree[4*N], n, m;
void pushup(int cur)
{
    tree[cur]=tree[2*cur]+tree[2*cur+1];
    return ;
}
void build(int cur, int lt, int rt)
{
    if(lt==rt)
    {
        tree[cur]=a[lt];
        return ;
    }
    int mid=(lt+rt)>>1;
    build(cur*2,lt,mid);
    build(cur*2+1,mid+1,rt);
    pushup(cur);
    return ;
}
int query(int cur, int lt, int rt, int qx, int qy)
{
    if(qy<lt||qx>rt)
    {
        return 0;
    }
    if(qx<=lt&&rt<=qy)
    {
        return tree[cur];
    }
    int mid=lt+rt>>1;
    return query(cur*2,lt,mid,qx,qy)+query(cur*2+1,mid+1,rt,qx,qy);
}
void update(int cur, int lt, int rt, int qx, int qy, int val)
{
    if(qy<lt||qx>rt)
    {
        return ;
    }
    if(lt==rt)
    {
        tree[cur]+=val;
        return ;
    }
    int mid=lt+rt>>1;
    update(cur*2,lt,mid,qx,qy,val);
    update(cur*2+1,mid+1,rt,qx,qy,val);
    pushup(cur);
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];  
    }
    build(1,1,n);
    while(m--)
    {
        int opt, x, y, val;
        cin>>opt>>x>>y;
        if(opt==1)
        {
            cin>>val;
            update(1,1,n,x,y,val);
        }
        if(opt==2)
        {
            cout<<query(1,1,n,x,y)<<"\n";
        }
    }
}

线段树的优化

很容易发现，单次修改的时间复杂度很慢。

考虑优化，采用懒标记。

性质：线段树的修改是为询问而服务的。

维护标记 tag_{cur} 表示结点 cur 需要修改的值。

修改后 update 函数单次时间复杂度可达 O(\log_2^n)

优化后代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int a[N], n, m, tag[4*N], tree[4*N];
void pushup(int cur)
{
    tree[cur]=tree[cur*2]+tree[cur*2+1];
    return ;
}
void addtag(int cur, int lt, int rt, int val)
{
    tag[cur]+=val;
    tree[cur]+=(rt-lt+1)*val;
    return ;
}
void pushdown(int cur, int lt, int rt)
{
    if(tag[cur]==0)
    {
        return ;
    }
    int mid=lt+rt>>1;
    addtag(cur*2,lt,mid,tag[cur]);
    addtag(cur*2+1,mid+1,rt,tag[cur]);
    tag[cur]=0;
    return ;
} 
void build(int cur, int lt, int rt)
{
    if(lt==rt)
    {
        tree[cur]=a[lt];
        return ;
    }
    int mid=lt+rt>>1;
    build(cur*2,lt,mid);
    build(cur*2+1,mid+1,rt);
    pushup(cur);
    return ;
}
int query(int cur, int lt, int rt, int qx, int qy)
{
    if(qy<lt||qx>rt)
    {
        return 0;
    }
    if(qx<=lt&&rt<=qy)
    {
        return tree[cur];
    }
    pushdown(cur,lt,rt);
    int mid=lt+rt>>1;
    return query(cur*2,lt,mid,qx,qy)+query(cur*2+1,mid+1,rt,qx,qy);
}
void update(int cur, int lt, int rt, int qx, int qy, int val)
{
    if(qy<lt||qx>rt)
    {
        return ;
    }
    if(qx<=lt&&rt<=qy)
    {
        addtag(cur,lt,rt,val);
        return ;
    }
    pushdown(cur,lt,rt);
    int mid=lt+rt>>1;
    update(cur*2,lt,mid,qx,qy,val);
    update(cur*2+1,mid+1,rt,qx,qy,val);
    pushup(cur);
    return ;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,1,n);
    while(m--)
    {
        int opt, x, y, val;
        cin>>opt>>x>>y;
        if(opt==1)
        {
            cin>>val;
            update(1,1,n,x,y,val);
        }
        else
        {
            cout<<query(1,1,n,x,y)<<"\n";
        }
    }
    return 0;
}

带乘法的线段树

多维护一个乘法标记，随加法标记更新，注意运算顺序。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int a[N], n, m, tag[4*N], tree[4*N], mod, mul[4*N];
void pushup(int cur)
{
    tree[cur]=tree[cur*2]%mod+tree[cur*2+1]%mod;
    return ;
}
void addtag(int cur, int lt, int rt, int val)
{
    tag[cur]+=val;
    tree[cur]+=(rt-lt+1)*val%mod;
    return ;    
}
void addtag1(int cur, int lt, int rt, int val)
{
    tag[cur]=tag[cur]*val%mod;
    mul[cur]=mul[cur]*val%mod;
    tree[cur]=tree[cur]*val%mod;
    return ;
}
void pushdown(int cur, int lt, int rt)
{
    if(tag[cur]==0&&mul[cur]==1)
    {
        return ;
    }
    int mid=(lt+rt)>>1;
    addtag1(cur*2,lt,mid,mul[cur]);
    addtag1(cur*2+1,mid+1,rt,mul[cur]);
    addtag(cur*2,lt,mid,tag[cur]);
    addtag(cur*2+1,mid+1,rt,tag[cur]);
    tag[cur]=0;
    mul[cur]=1;
    return ;
} 
void build(int cur, int lt, int rt)
{
    if(lt==rt)
    {
        tree[cur]=a[lt];
        return ;
    }
    int mid=lt+rt>>1;
    build(cur*2,lt,mid);
    build(cur*2+1,mid+1,rt);
    pushup(cur);
    return ;
}
int query(int cur, int lt, int rt, int qx, int qy)
{
    if(qy<lt||qx>rt)
    {
        return 0;
    }
    if(qx<=lt&&rt<=qy)
    {
        return tree[cur];
    }
    pushdown(cur,lt,rt);
    int mid=lt+rt>>1;
    return query(cur*2,lt,mid,qx,qy)+query(cur*2+1,mid+1,rt,qx,qy);
}
void update(int cur, int lt, int rt, int qx, int qy, int val)
{
    if(qy<lt||qx>rt)
    {
        return ;
    }
    if(qx<=lt&&rt<=qy)
    {
        addtag(cur,lt,rt,val);
        return ;
    }
    pushdown(cur,lt,rt);
    int mid=lt+rt>>1;
    update(cur*2,lt,mid,qx,qy,val);
    update(cur*2+1,mid+1,rt,qx,qy,val);
    pushup(cur);
    return ;
}
void update1(int cur, int lt, int rt, int qx, int qy, int val)
{
    if(qy<lt||qx>rt)
    {
        return ;
    }
    if(qx<=lt&&rt<=qy)
    {
        addtag1(cur,lt,rt,val);
        return ;
    }
    pushdown(cur,lt,rt);
    int mid=lt+rt>>1;
    update1(cur*2,lt,mid,qx,qy,val);
    update1(cur*2+1,mid+1,rt,qx,qy,val);
    pushup(cur);
    return ;
}
signed main()
{
    cin>>n>>m>>mod;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=4*n;i++)
    {
        mul[i]=1;
    }
    build(1,1,n);
    while(m--)
    {
        int opt, x, y, val;
        cin>>opt>>x>>y;
        if(opt==2)
        {
            cin>>val;
            update(1,1,n,x,y,val);
        }
        else if(opt==1)
        {
            cin>>val;
            update1(1,1,n,x,y,val);
        }
        else
        {
            cout<<query(1,1,n,x,y)%mod<<"\n";
        }
    }
    return 0;
}

例题 https://www.luogu.com.cn/problem/CF240F

分析

统计一段区间 [L,R] 中每种字母出现的次数，若奇数出现的次数最多 1 次，则可以回文。

若有 1 种字母出现奇数次，则中间位置放该字母，剩下的字母按照字典序依次放。

每种字母维护一棵关于下标的线段树，数值为 1 或 0 表示出现/没出现该字母。

询问时，对 26 种字母 query()，并统计奇数出现的次数 cnt，若 cnt>1 则无解，不修改。

修改时，对每一种字母做区间修改，最多 26 次。

O(m \times 26 \times log_2 n)

权值线段树 Weighted segment tree

概念

指线段树的结点管辖的不是一段下标，而是一段值域。

通俗点讲，就是，

线段树的每个结点是用来维护一段区间的最大值或总和；

而权值线段树的每个结点储存的一段区间有多少个数；

作用

权值线段树主要用来求区间第 k 大值或区间第 k 小值。

例题① —— P1637 三元上升子序列

题目传送门

题目大意

在 a 数组中统计满足 i<j<k 且 a_i<a_j<a_k 的三元组 {i,j,k} 的数量（1\le i,j,k \le n）。

暴力100分思路

两重循环枚举，第一层枚举中心点 j，第二次循环从 1 扫到中心点前求 i 可能的数量，再第二层循环从中心点后扫到 n，求 k 可能的数量，最后将它们相乘。

暴力100分代码（拒绝抄袭，已将所有代码加入防抄袭）

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100005];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int cnt1=0, cnt2=0;
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i])
            {
                cnt1++;
            }
        }
        for(int j=i+1;j<=n;j++)
        {
            if(a[i]<a[j])
            {
                cnt2++;
            }
        }
        ans+=cnt1*cnt2;
    }
    cout<<ans;
    return 1;
}

权值线段树优化

刚刚的暴力写法建立在题目不卡常的情况下，若题目卡常就寄了。这时我们可以用权值线段树优化时间复杂度。

从 1 到 50000 建一棵权值线段树，每次询问先前有多少个点 id 大于当前点并且已入线段树，最后在把对应权值处在线段树上 +1。

注意：

要统计两次分别是 i 和 k。
统计完第一次后要重新建树。

代码（已加防抄袭）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int a[N], n, m, tag[4*N], tree[4*N];
int cnt1[400005], cnt2[400005];
void pushup(int cur)
{
    tree[cur]=tree[cur*2]+tree[cur*2+1];
    return ;
}
void addtag(int cur, int lt, int rt, int val)
{
    tag[cur]+=val;
    tree[cur]+=(rt-lt+1)*val;
    return ;
}
void pushdown(int cur, int lt, int rt)
{
    if(tag[cur]==0)
    {
        return ;
    }
    int mid=lt+rt>>1;
    addtag(cur*2,lt,mid,tag[cur]);
    addtag(cur*2+1,mid+1,rt,tag[cur]);
    tag[cur]=0;
    return ;
} 
void build(int cur, int lt, int rt)
{
    if(lt==rt)
    {
        tree[cur]=0;
        return ;
    }
    int mid=lt+rt>>1;
    build(cur*2,lt,mid);
    build(cur*2+1,mid+1,rt);
    pushup(cur);
    return ;
}
int query(int cur, int lt, int rt, int qx, int qy)
{
    if(qy<lt||qx>rt)
    {
        return 0;
    }
    if(qx<=lt&&rt<=qy)
    {
        return tree[cur];
    }
    pushdown(cur,lt,rt);
    int mid=lt+rt>>1;
    return query(cur*2,lt,mid,qx,qy)+query(cur*2+1,mid+1,rt,qx,qy);
}
void update(int cur, int lt, int rt, int qx, int qy, int val)
{
    if(qy<lt||qx>rt)
    {
        return ;
    }
    if(qx<=lt&&rt<=qy)
    {
        addtag(cur,lt,rt,val);
        return ;
    }
    pushdown(cur,lt,rt);
    int mid=lt+rt>>1;
    update(cur*2,lt,mid,qx,qy,val);
    update(cur*2+1,mid+1,rt,qx,qy,val);
    pushup(cur);
    return ;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,1,1e5);
    for(int i=1;i<=n;i++)
    {
        cnt1[i]=query(1,1,1e5,1,a[i]-1);
        update(1,1,1e5,a[i],a[i],1);
    }
    build(1,1,1e5);
    int ans=0;
    for(int i=n;i>=1;i--)
    {
        cnt2[i]=query(1,1,1e5,a[i]+1,1e5);
        update(1,1,1e5,a[i],a[i],1);
        ans+=cnt1[i]*cnt2[i];
    }
    cout<<ans;
    return 0;
}

例题②—— P1908 逆序对

题目传送门

题目大意

求 a 数组中 a_i>a_j 且 i<j 的二元组 {i,j}。

权值线段树解法

就不写暴力了，快速进入正题。

这题跟上题很相似，唯一不同的两点是本题建树只建一次和要从小到大排序。

代码（加防抄袭）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5;
struct node
{
    int v, id;
}a[N];
int n, m, tag[4*N], tree[4*N];
int cnt1[400005], cnt2[400005];
bool cmp(node x, node y)
{
    if(x.v==y.v)
    {
        return x.id<y.id; 
    }
    return x.v<y.v;
}
void pushup(int cur)
{
    tree[cur]=tree[cur*2]+tree[cur*2+1];
    return ;
}
void addtag(int cur, int lt, int rt, int val)
{
    tag[cur]+=val;
    tree[cur]+=(rt-lt+1)*val;
    return ;
}
void pushdown(int cur, int lt, int rt)
{
    if(tag[cur]==0)
    {
        return ;
    }
    int mid=lt+rt>>1;
    addtag(cur*2,lt,mid,tag[cur]);
    addtag(cur*2+1,mid+1,rt,tag[cur]);
    tag[cur]=0;
    return ;
} 
void build(int cur, int lt, int rt)
{
    if(lt==rt)
    {
        tree[cur]=0;
        return ;
    }
    int mid=lt+rt>>1;
    build(cur*2,lt,mid);
    build(cur*2+1,mid+1,rt);
    pushup(cur);
    return ;
}
int query(int cur, int lt, int rt, int qx, int qy)
{
    if(qy<lt||qx>rt)
    {
        return 0;
    }
    if(qx<=lt&&rt<=qy)
    {
        return tree[cur];
    }
    pushdown(cur,lt,rt);
    int mid=lt+rt>>1;
    return query(cur*2,lt,mid,qx,qy)+query(cur*2+1,mid+1,rt,qx,qy);
}
void update(int cur, int lt, int rt, int qx, int qy, int val)
{
    if(qy<lt||qx>rt)
    {
        return ;
    }
    if(qx<=lt&&rt<=qy)
    {
        addtag(cur,lt,rt,val);
        return ;
    }
    pushdown(cur,lt,rt);
    int mid=lt+rt>>1;
    update(cur*2,lt,mid,qx,qy,val);
    update(cur*2+1,mid+1,rt,qx,qy,val);
    pushup(cur);
    return ;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].v;
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmp);
    build(1,1,5e5);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=query(1,1,5e5,a[i].id+1,5e5);
        update(1,1,5e5,a[i].id,a[i].id,1);
    }
    cout<<ans;
    return 0;
}

树形 DP

含义&分类

树形 DP，顾名思义，在树形结构上的 DP 问题。

按照题目可将树形 DP 分为两类：

第一类：兄弟子树之间无数量依赖关系的 DP。

第二类：兄弟子树之间有数量依赖关系的 DP（实际上就是树上背包）。

第一类树形 DP 超详解

例题①：P1122

简要题意：

给定 n 个点，n-1 条边的树，点权为 val_i，求删一些边后，剩下的子树的最大权值和。

分析

这道题适合刚学的同学们当作模版题去理解。首先先从这道题需要用到的算法入手。由题面可知，本题中小的子树可以向大的子树转移，且无后效性，可以考虑树形 DP。

DP 四步法——状态、答案、状态转移方程和初始状态。

First step：状态

这种状态的定义方式几乎贯穿整个树形 DP。 #### Second step：答案 $dp_i$ 取最大值。 #### Third step：状态转移方程由于可以把根结点以下的部分全删了也可以不删，所以要对答案取最大值（因为一个结点可能有多个子结点）。枚举当前结点 $cur$ 的每一个子结点 $nxt$，深搜。 $dp_{cur}=\max(dp_{cur},dp_{cur}+dp_{nxt})

Fourth step：初始状态

#### 注意事项先递归，再转移。 #### 代码 ```cpp #include<bits/stdc++.h> #define int long long using namespace std; int n, dp[16005], ans=LONG_LONG_MIN, a[16005]; vector<int> nbr[16005]; void dfs(int cur, int fa) { dp[cur]=a[cur]; for(int nxt:nbr[cur]) { if(nxt==fa) { continue; } dfs(nxt,cur); dp[cur]=max(dp[cur],dp[cur]+dp[nxt]); } ans=max(ans,dp[cur]); } signed main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } for(int i=1;i<n;i++) { int x, y; cin>>x>>y; nbr[x].push_back(y); nbr[y].push_back(x); } dfs(1,0); cout<<ans; } ``` ### 练习题①——[P1352](/problem/P1352) #### 简要题意：给定一棵带点权的有根树，父节点选了，子结点就不能选，求如何选取结点使权值和最大。 #### First step：状态 $dp_{i,0/1}$ 表示以 $i$ 为根结点的子树，且 $i$ 选或不选的最大权值和。 #### Second step：答案 $\max(dp_{root,0},dp_{root,1})$。 #### Third step 状态转移方程 $dp_{cur,0}+=\max(dp_{nxt,0},dp_{nxt,1})

dp_{cur,1}+=dp_{nxt,0}

Fourth step：初始状态

## 第二类树形 DP ### 例题①——[P2015](/problem/P2015) #### First step：状态 $dp_{i,j}$ 表示以 $i$ 为根的子树保留 $j$ 条边的最大权值和。 #### Second step：答案 $dp_{1,q}$。 #### Third step：状态转移方程 ``` for(auto i:nbr[cur]) { int nxt=i.y, w=i.val; if(nxt==fa) { continue; } sum+=dfs(nxt,cur)+1; for(int v=q;v>-1;v--) { for(int k=0;k<v;k++) { dp[cur][v]=max(dp[cur][v],dp[cur][v-k-1]+dp[nxt][k]+w); } } } ``` # 强连通分量（SCC，Strongly Connected Components） ## 定义 ### 强连通有向图（DAG）中若其中两点 $x$，$y$ 能彼此到达（不一定是直接连边），称 $x$ 和 $y$ 是强连通的。 ![](https://s11.ax1x.com/2024/01/31/pFMegKJ.png) 下图中 $1$ 和 $7$ 是其中一组强连通的点对。 ### 强连通分量有向图 $G$ 中存在一个极大子图 $G1$，$G1$ 内任意 $2$ 点都是强连通的，且 $G1$ 不能包含更多的点，那么 $G1$ 为 $G$ 的一个 SCC。注意：强连通分量要么是 $1$ 个单点，要么是 $1$ 个环。 ## 如何寻找强连通分量 ### 法1——Tarjan 算法 #### 引入 Robert E. Tarjan（罗伯特·塔扬，1948~），生于美国加州波莫纳，计算机科学家。 Tarjan 发明了很多算法和数据结构。不少他发明的算法都以他的名字命名，以至于有时会让人混淆几种不同的算法。比如求各种连通分量的 Tarjan 算法，求 LCA（Lowest Common Ancestor，最近公共祖先）的 Tarjan 算法。并查集、Splay、Toptree 也是 Tarjan 发明的。 #### 前置知识——时间戳也称 $dfs$ 序。表示从源点开始搜索 $x$ 是第几个被搜到的。 #### 前置知识——关键点指搜索到每个环时第一个被搜到的环内点。特征（设某一关键点为 $x$）：`dfn[x]==low[x]`。 #### 过程 Tarjan 是所有求强连通分量的算法中最常见也最实用的算法，基于 dfs（深度优先搜索，Deep First Search）算法。定义数组 $dfn_x$ 表示点 $x$ 在 $dfs$ 搜索中的最小时间戳；$low_x$ 表示点 $x$ 能走到的点的最小时间戳。 $dfn_x$ 的维护：定义计数器 $cnt$，每 $dfs$ 一次，`cnt++,dfn[x]=cnt`。 $low_x$ 的维护：初始时 `low[x]=dfn[x]`，在回溯后对 $x$ 指向的点的 $low$ 或 $dfn$ 取最小值。 ##### $low_x$ 维护代码 ```cpp for(int nxt:nbr[cur]) { if(!dfn[nxt]) { tarjan(nxt); low[cur]=min(low[cur],low[nxt]); } else if(viss[nxt]) { low[cur]=min(low[cur],dfn[nxt]); } } ``` 最后若 $dfn[x]==low[x]$，将站内位置在 $x$ 以上的所有结点以及 $x$ 出栈（已确认这些结点属于这个 SCC），而且可以确定多了一个强连通分量。时间复杂度：$O(n + m)

Tarjan 代码

void tarjan(int cur)
{
    stk.push(cur);
    viss[cur]=1;
    low[cur]=dfn[cur]=++cnt;
    for(int nxt:nbr[cur])
    {
        if(!dfn[nxt])
        {
            tarjan(nxt);
            low[cur]=min(low[cur],low[nxt]);
        }
        else if(viss[nxt])
        {
            low[cur]=min(low[cur],dfn[nxt]);
        }
    }
    if(dfn[cur]==low[cur])
    {
        sum++;
        while(stk.top()!=cur)
        {
            int tmp=stk.top();
            stk.pop();
            scc[tmp]=sum;
            ans[sum].push_back(tmp);
            viss[tmp]=0;
        }
        stk.pop();
        ans[sum].push_back(cur);
        scc[cur]=sum;
        viss[cur]=0;
    }
}

法2——Kosaraju 算法

引入

Kosaraju 算法由 S. Rao Kosaraju 在 1978 年一篇未发表的论文中提出，但 Micha Sharir 最早发表了它。

过程

创建反图。

两遍 dfs。

第一次 dfs，选取任意顶点作为起点，遍历所有未访问过的顶点，并在回溯之前给顶点编号，也就是后序遍历。

第二次 dfs，对于反向后的图，以标号最大的顶点作为起点开始 DFS。这样遍历到的顶点集合就是一个强连通分量。对于所有未访问过的结点，选取标号最大的，重复上述过程。

两次 dfs 结束后，强连通分量就找出来了，Kosaraju 算法的时间复杂度为 O(n+m)。

由于 Kosaraju 算法应用面没有 Tarjan 算法广，故在此几笔带过。

Kosaraju 代码

void dfs1(int u) {
  vis[u] = true;
  for (int v : g[u])
    if (!vis[v]) dfs1(v);
  s.push_back(u);
}

void dfs2(int u) {
  color[u] = sccCnt;
  for (int v : g2[u])
    if (!color[v]) dfs2(v);
}

void kosaraju() {
  sccCnt = 0;
  for (int i = 1; i <= n; ++i)
    if (!vis[i]) dfs1(i);
  for (int i = n; i >= 1; --i)
    if (!color[s[i]]) {
      ++sccCnt;
      dfs2(s[i]);
    }
}

其中 g 是原图，g2 是反图。

法3——Garbow 算法

Garbow 算法是 Tarjan 算法的另一种实现（注意，并不是优化），Tarjan 算法是用 dfn 和 low 来计算强连通分量的根，Garbow 维护一个节点栈，并用第二个栈来确定何时从第一个栈中弹出属于同一个强连通分量的节点。

从节点 w 开始的 dfs 过程中，当一条路径显示这组节点都属于同一个 SCC 时，只要栈顶节点的时间戳大于根节点 w 的时间戳，就从第二个栈中弹出这个节点，那么最后只留下根节点 w。

在这个过程中每一个被弹出的节点都属于同一个 SCC。

当回溯到某一个节点 w 时，如果这个节点在第二个栈的顶部，就说明这个节点是 SCC 的起始节点，在这个节点之后搜索到的那些节点都属于同一个 SCC，于是从第一个栈中弹出那些节点，构成 SCC。

Garbow 算法的时间复杂度为 O(n+m)。

由于 Tarjan 算法的广泛出现，Garbow 算法没有人会系统的学习，故在此几笔带过。

Garbow 代码

int garbow(int u) {
  stack1[++p1] = u;
  stack2[++p2] = u;
  low[u] = ++dfs_clock;
  for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (!low[v])
      garbow(v);
    else if (!sccno[v])
      while (low[stack2[p2]] > low[v]) p2--;
  }
  if (stack2[p2] == u) {
    p2--;
    scc_cnt++;
    do {
      sccno[stack1[p1]] = scc_cnt;
      // all_scc[scc_cnt] ++;
    } while (stack1[p1--] != u);
  }
  return 0;
}

void find_scc(int n) {
  dfs_clock = scc_cnt = 0;
  p1 = p2 = 0;
  memset(sccno, 0, sizeof(sccno));
  memset(low, 0, sizeof(low));
  for (int i = 1; i <= n; i++)
    if (!low[i]) garbow(i);
}

例题：B3609 [图论与代数结构 701] 强连通分量

题目描述

给定一张 n 个点 m 条边的有向图，求出其所有的强连通分量。

注意，本题可能存在重边和自环。

输入格式

第一行两个正整数 n ， m ，表示图的点数和边数。

接下来 m 行，每行两个正整数 u 和 v 表示一条边。

输出格式

第一行一个整数表示这张图的强连通分量数目。

接下来每行输出一个强连通分量。第一行输出 1 号点所在强连通分量，第二行输出 2 号点所在强连通分量，若已被输出，则改为输出 3 号点所在强连通分量，以此类推。每个强连通分量按节点编号大小输出。

样例 #1

样例输入 #1

样例输出 #1

提示

对于所有数据，1 \le n \le 10000，1 \le m \le 100000。

代码+解析注释——Tarjan

本题主要难点在第二问“接下来每行输出一个强连通分量。第一行输出 1 号点所在强连通分量，第二行输出 2 号点所在强连通分量，若已被输出，则改为输出 3 号点所在强连通分量，以此类推。每个强连通分量按节点编号大小输出。”上。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int low[N], dfn[N], cnt, sum, scc[N], n, m;
bool viss[N];
stack<int> stk;
vector<int> nbr[N], ans[N];
void tarjan(int cur)//找 SCC
{
    stk.push(cur);
    viss[cur]=1;
    low[cur]=dfn[cur]=++cnt;
    for(int nxt:nbr[cur])
    {
        if(!dfn[nxt])
        {
            tarjan(nxt);
            low[cur]=min(low[cur],low[nxt]);
        }
        else if(viss[nxt])
        {
            low[cur]=min(low[cur],dfn[nxt]);
        }
    }
    if(dfn[cur]==low[cur])
    {
        sum++;
        while(stk.top()!=cur)
        {
            int tmp=stk.top();
            stk.pop();
            scc[tmp]=sum;
            ans[sum].push_back(tmp);
            viss[tmp]=0;
        }
        stk.pop();
        ans[sum].push_back(cur);
        scc[cur]=sum;
        viss[cur]=0;
    }
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u, v;
        cin>>u>>v;
        nbr[u].push_back(v);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            tarjan(i);
        }
    }
    cout<<sum<<"\n";
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==0)
        {
            continue;
        }
        sort(ans[scc[i]].begin(), ans[scc[i]].end());//vector 从小到大排序
        for(int cur:ans[scc[i]])
        {
            cout<<cur<<" ";
            dfn[cur]=0;
        }
        cout<<"\n";
    }
}

动态数组 ans 表示每个 SCC 包含的点。第二问将每个 SCC 的点排个序然后输出即可。

强连通分量试炼场

difficult 1

P1455 搭配购买

P3916 图的遍历

difficult 1 例题详解——P3916

先 Tarjan 缩点。

在同一个 SCC 中的点可以相互到达，那么我们可以在缩点时记录每个 SCC 中编号最大的点。

一个 SCC 中所有点能到达的最大编号的点即为这个 SCC 能到达的最大的编号。

缩点代码就不放了，在这里提供普通 dfs 的代码。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, ans[1000005];
vector<int> nbr[100005];
void dfs(int cur, int maxi)
{
    if(ans[cur]!=0)
    {
        return ;
    }
    ans[cur]=maxi;
    for(int nxt:nbr[cur])
    {
        dfs(nxt,maxi);
    }
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x, y;
        cin>>x>>y;
        nbr[y].push_back(x);
    }
    for(int i=n;i>=1;i--)
    {
        if(ans[i]==0)
        {
            dfs(i,i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<" ";
    }
}

difficult 2

P3387 【模板】缩点

P2863 USACO06JAN The Cow Prom S

P2341 USACO03FALL / HAOI2006 受欢迎的牛 G

P2002 消息扩散

P1073 NOIP2009 提高组最优贸易

difficult 2 例题详解——P3387

先来看一张图

在这个图中，有 5 个 SCC。

将这 5 个 SCC 缩成一个点，得到 5 个新点 a,b,c,d,e。

其中

点 1 --------> 点 a

点 2,3,4,5 --------> 点 b

点 6 --------> 点 c

点 7,8,9 --------> 点 d

点 10 --------> 点 e

这就是所谓的缩点，缩成的点的点权为原 SCC 内点权之和。这也是本题的重要思想。

为什么要缩点呢？在本题中，点权最大的路径可以使用拓扑排序+dp，但拓扑排序的前提是有向无环图（DAG），而本题明显有环。缩点就让环变成一个点了。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
vector<int>nbr[maxn];
stack<int>stk;
int in[maxn];
int a[maxn], sum[maxn];
int dp[maxn];
int n, m, dfn[maxn], used[maxn], vis[maxn], low[maxn], scc[maxn], num[maxn], cntc, cnt, ans;
struct node
{
    int x, y;
}e[maxn];
void tarjan(int cur)
{
    dfn[cur]=low[cur]=++cnt;
    stk.push(cur);
    for(int q:nbr[cur])
    {
        if(!dfn[q])
        {
            tarjan(q);
            low[cur]=min(low[cur],low[q]);
        }
        else if(!scc[q]) 
        {
            low[cur]=min(low[cur],dfn[q]);
        }
    }
    if(low[cur]==dfn[cur])
    {
        cntc++;
        scc[cur]=cntc;
        num[cntc]++;
        while(stk.top()!=cur)
        {
            int t=stk.top();
            stk.pop();
            scc[t]=cntc;
            num[cntc]++;
        }
        stk.pop();
    }
}
void topo()
{
    queue<int> q;
    for(int i=1;i<=cntc;i++)
    {
        if(in[i]==0)
        {
            q.push(i);
            dp[i]=sum[i];
        }
    }
    while(q.empty()==0)
    {
        int cur=q.front();
        q.pop();
        for(int nxt:nbr[cur])
        {
            in[nxt]--;
            dp[nxt]=max(dp[nxt],dp[cur]+sum[nxt]);
            if(in[nxt]==0)
            {
                q.push(nxt);
            }
        } 
    }
    int maxi=-1e9;
    for(int i=1;i<=cntc;i++)
    {
        maxi=max(maxi,dp[i]);
    }
    cout<<maxi;
    return ;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>e[i].x>>e[i].y;
        nbr[e[i].x].push_back(e[i].y);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            tarjan(i);
        } 
    }
    for(int i=1;i<=n;i++)
    {
        sum[scc[i]]+=a[i];
    }
    for(int i=1;i<=10004;i++)
    {
        nbr[i].clear();
    }
    for(int i=1;i<=m;i++)
    {
        if(scc[e[i].x]!=scc[e[i].y])
        {
            nbr[scc[e[i].x]].push_back(scc[e[i].y]);
            in[scc[e[i].y]]++;
        }
    }
    topo(); 
    return 0;
}

difficult 2 例题详解——P2863

记录每个 SCC 的大小，最后判断是不是大于 1 并输出即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
vector<int>nbr[maxn];
stack<int>s;
int n, m, dfn[maxn], used[maxn], vis[maxn], low[maxn], color[maxn], num[maxn], cntc, cnt, ans;
void add(int x)
{
    s.pop();
    color[x]=cntc;
    num[cntc]++;
    vis[x]=false;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++cnt;
    s.push(x);
    vis[x]=used[x]=true;
    for(int q:nbr[x])
    {
        if(!dfn[q])
        {
            tarjan(q);
            low[x]=min(low[x],low[q]);
        }
        else if(vis[q]) 
        {
            low[x]=min(low[x],dfn[q]);
        }
    }
    if(low[x]==dfn[x])
    {
        cntc++;
        while(s.top()!=x)
        {
            int t=s.top();
            add(t);
        }
        add(x);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        nbr[u].push_back(v);
    }
    for(int i=1;i<=n;i++)
    {
        if(!used[i])
        {
            tarjan(i);
        } 
    }
    for(int i=1;i<=cntc;i++)
    {
        if (num[i]>1)
        {
            ans++;
        } 
    }
    cout<<ans;
    return 0;
}

difficult 2 例题详解——P2341

Tarjan

由题可得，受欢迎的奶牛只有可能是图中唯一的入度为零的强连通分量中的所有奶牛，所以若出现两个以上入度为 0 的强连通分量则不存在明星奶牛。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
vector<int>nbr[maxn];
stack<int>s;
int ans1=0;
int in[maxn];
int a[maxn];
int n, m, dfn[maxn], used[maxn], vis[maxn], low[maxn], color[maxn], num[maxn], cntc, cnt, ans;
void add(int x)
{
    color[x]=cntc;
    num[cntc]++;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++cnt;
    s.push(x);
    for(int q:nbr[x])
    {
        if(!dfn[q])
        {
            tarjan(q);
            low[x]=min(low[x],low[q]);
        }
        else if(!color[q]) 
        {
            low[x]=min(low[x],dfn[q]);
        }
    }
    if(low[x]==dfn[x])
    {
        cntc++;
        add(x);
        while(s.top()!=x)
        {
            int t=s.top();
            add(t);
            s.pop();
        }
        s.pop();
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        nbr[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            tarjan(i);
        } 
    }
    for(int i=1;i<=n;i++)
    {
        for(int nxt:nbr[i])
        {
            if(color[i]!=color[nxt])
            {
                in[color[nxt]]++;
            }
        }
    }
    int ans=0, cntu=0;
    for(int i=1;i<=cntc;i++)
    {
        if(!in[i])
        {
            ans=num[i];
            cntu++;
        } 
    }
    if(cntu==1)cout<<ans;
    else cout<<0;
    return 0;
}

difficult PRO

放几道题在这，难度很大，诸位加油~。

P1262 间谍网络

P3627 APIO2009 抢掠计划

UVA11324 The Largest Clique

P2746 USACO5.3 校园网Network of Schools

P2812 校园网络【USACO Network of Schools加强版】

P1407 国家集训队稳定婚姻

P2169 正则表达式

P4819 中山市选 sr游戏

P2403 SDOI2010 所驼门王的宝藏

P4339 ZJOI2018 迷宫

P4233 射命丸文的笔记

CF949C

P3275 [SCOI2011] 糖果

difficult PRO 例题详解——P1407

分析

在给定的 n 组关系中，B 向 G 建边。在给定的 m 组情侣中，G 向 B 建边。若关系不稳定，则一定有环，若 scc_{B_i}=scc_{G_i}，则第 i 组关系不稳定，否则稳定。

difficult PRO 例题详解——P1262

题意

#### 分析若图是有向无环图，那么贪心的选择入度为 $0$ 的点最优，若存在入度为 $0$ 的点 $x$，且 $x$ 没有点权，无解。若有解，入度为 $0$ 的所有点的权值之和即为答案。若图中存在环，那么只需要用环上点权最小的值代表整个“大点”。细节上，没有点权可以设为极大值 $10^9$。第一个权值为 $10^9$ 的开始 $tarjan$ 的点就是无法控制的最小编号。 $O(n+r)$。 ### difficult PRO 例题详解——P3275 - 若 $a<b$，可以理解为 $a$ 的糖果数至少比 $b$ 少 $1$ 颗。$a$ 向 $b$ 连边，权值为 $1$。 - 若 $a>b$，$b$ 向 $a$ 连边，权值为 $1$。 - 若 $a \le b$，从贪心的角度，取等于最好，$a$ 向 $b$ 连边，权值为$0$。 - 若 $a \ge b$，$b$ 向 $a$ 连边，权值为$0$。 - 若 $a=b$，则 $a$ 向 $b$，$b$ 向 $a$ 连边，权值均为 $0$。若该图是有向无环图，定义 $dp_i$ 表示点 $i$ 最少发的糖果数。转移：$cur->nxt$，则 $dp_{nxt}=\max(dp_{nxt},dp_{cur}+w)

答案：ans+=dp_i

初始状态：dp_i=1

若有环，则先缩点，若环上有边权为 1，则无解。

difficult PRO 例题详解——P2746

提炼大意

给定 n 个点若干条有向边。

目标 1：求最少发几个软件，使得 n 个点都能得到。

目标 2：最少连几条边，使得无论发 1 个软件给哪个点其余点都能得到。

分析

跑 Tarjan 缩点，建新图，统计入度。
入度为 0 的强连通分量（SCC）的个数就是答案 1。
入度为 0 的强连通分量（SCC）和出度为 0 的强连通分量（SCC）的个数的较大值为答案 2。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n, m, a[N], num[N], low[N], dfn[N], in[N], sum[N], cnt, cntc, scc[N];
bool viss[N];
struct node
{
    int x, y;
}e[N<<2];
queue<int> q;
int dp[N], out[N];
vector<int> nbr[N];
stack<int> stk;
void tarjan(int cur)
{
    low[cur]=dfn[cur]=++cnt;
    viss[cur]=1;
    stk.push(cur);
    for(int nxt:nbr[cur])
    {
        if(!dfn[nxt])
        {
            tarjan(nxt);
            low[cur]=min(low[cur],low[nxt]);
        }
        else if(viss[nxt])
        {
            low[cur]=min(low[cur],dfn[nxt]);
        }
    }
    if(dfn[cur]==low[cur])
    {
        cntc++;
        scc[cur]=cntc;
        num[cntc]++;
        viss[cur]=0;
        while(stk.top()!=cur)
        {
            int nxt=stk.top();
            stk.pop();
            num[cntc]++;
            viss[nxt]=0;
            scc[nxt]=cntc;
        }
        stk.pop();
    }
}
int cntd=0;
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        while(cin>>x)
        {
            if(x==0)
            {
                break;
            }
            nbr[i].push_back(x);
            cntd++;
            e[cntd].x=i;

            e[cntd].y=x;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            tarjan(i);
        }
    }
    int ind=0, outd=0;
    for(int i=1;i<=cntd;i++)
    {
        if(scc[e[i].x]!=scc[e[i].y])
        {
            in[scc[e[i].y]]++;
            out[scc[e[i].x]]++;
        }
    }
    for(int i=1;i<=cntc;i++)
    {
        ind+=!in[i];
        outd+=!out[i];
    }
    if(cntc==1)
    {
        cout<<ind<<"\n"<<0;
    }
    else
    {
        cout<<ind<<"\n"<<max(ind,outd);
    }
}

单调队列

定义

是指队列维护的元素单调、下标也单调的数据结构。

单调队列不像优先队列，是一种C++自带的STL，单调队列是用普通的队列进行维护的。

使用场景

滑动窗口。

在一个固定大小的窗口内寻找最值，且窗口从左到右移动。

滑动窗口实现方法

暴力：O(n^2)
线段树：O(n \times \log_2{n})。
RMQ：O(n \times \log_2{n})
单调队列：O(n)

显然，用单调队列维护时间复杂度最优。

单调队列实现步骤

循环枚举下标 i，从 1 到 n。
检查队头是否过期，并从队头删除过期下标。
输出队头元素，即为当前窗口最大值（具体看题目）。

时间复杂度分析：每个元素只出队入队一次，总时间复杂度为 O(n)

例题

First：P1886、P2032

单调队列模板题。

系列难度：P2032 < P1886

放个P1886的代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int a[N], q[N], n, k, head=1, tail;
void getmin()
{
    head=1, tail=0;
    for(int i=1;i<=n;i++)
    {
        while(head<=tail&&a[q[tail]]>=a[i])
        {
            tail--;
        }
        q[++tail]=i;
        while(head<=tail&&q[tail]-q[head]+1>k)
        {
            head++;
        }
        if(i>=k)cout<<a[q[head]]<<" ";
    }
    cout<<"\n";
}
void getmax()
{
    memset(q,0,sizeof(q));
    head=1, tail=0;
    for(int i=1;i<=n;i++)
    {
        while(head<=tail&&a[q[tail]]<=a[i])
        {
            tail--;
        }
        q[++tail]=i;
        while(head<=tail&&q[tail]-q[head]+1>k)
        {
            head++;
        }
        if(i>=k)cout<<a[q[head]]<<" ";
    }
    cout<<"\n";
}
signed main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    getmin();
    getmax();
}

Second：P1638、P1440

稍微包装了一下的模板题。

系列难度：P1638 > P1440

Third：P1714

单调队列中套了一个简单算法，这次套的前缀和。

Fourth：P2698、P2564

难度上升了不止一点。

P2698在二次单调队列中套了个二分。

难度都差不多，P2564有一些坑点，P2698难写一些。

P2698也有坑点，和单调队列窗口大小有关。

总结

单调队列虽然是线段树等数据结构中难度中下级的数据结构，但与其他算法结合起来难度还是不小的。

单调队列例题

讲个难点的，P2698

分析

由于每滴水以 1 单位时间下降，所以时间差等于高度差。
假设花盆宽度 w 已经确定，那么花盆可以从左到右滑动，转化为滑动窗口。
维护 2 个单调队列，维护最小和最大 y 值。
枚举花盆宽度可行但会TLE，宽度有单调性，一眼二分。

注意事项：

枚举将水滴按 x 轴 sort。（水滴比坐标小，枚举水滴常数低）
花盆宽度为 n 时，可接到 [i,i+w] 的水滴。

贴个 check 函数

bool check(int x)
{
    head=1,tail=0,head1=1,tail1=0;
    for(int i=1;i<=n;i++)
    {
        while(head<=tail&&a[i].y>=a[q[tail]].y)
        {
            tail--;
        }
        q[++tail]=i;
        while(tail-head>=0&&a[q[tail]].x-a[q[head]].x+1>x)
        {
            head++;
        }
        while(head1<=tail1&&a[i].y<=a[qq[tail1]].y)
        {
            tail1--;
        }
        qq[++tail1]=i;
        while(tail1-head1>=0&&a[qq[tail1]].x-a[qq[head1]].x+1>x)
        {
            head1++;
        }
        if(abs(a[q[head]].y-a[qq[head1]].y)>=m)
        {
            return 1;
        }
    }
    return 0;
}

单调栈

定义

一种下标单调、元素也单调的栈。

单调栈同单调队列不是一种C++自带的STL，单调栈是用普通的栈进行维护的。

使用场景

在若干区间内找最值，转化为枚举每个最值找区间。

寻找每个元素 a_i 向右（左）第一个比 a_i 大（小）的元素位置。

如何寻找 a_i 右边第一个大于 a_i 的位置？

枚举 i，a_i 与 stk.top() 循环比较，若 a_i 大于当前栈顶元素，弹出栈顶。
循环结束后，剩余栈中元素下标说明其右侧没有更大的元素。

如何寻找 a_i 左边第一个大于 a_i 的位置？

同上，倒序枚举 i 即可。

训练题单

P5788 模板题
P2947 跟模板题差不多，套了个背景。
P2866 初学者建议去做，码量短，有少许思维难度。
CF547B 做法多样，难度中等偏上少许，有一定思维难度，记得看讨论区的翻译。
CF1299C 这题建议已开始学CSP-S相关内容的同学做，难度思维码量都有的。

模板代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e6+5;
int n, a[N], ans[N];

stack<int> stk;
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[n+1]=1e9;
    }
    for(int i=1;i<=n;i++)
    {
        while(!stk.empty()&&a[i]>a[stk.top()])
        {
            ans[stk.top()]=i;
            stk.pop();
        }
        stk.push(i);
    }
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<" ";
    }
    return 0;
}

单源最短路径

主要算法 Dijkstra 算法 & Bellman-Ford 算法

Dijkstra 算法

原理

以点为研究对象的贪心策略。

实现步骤

将图中的顶点分为已经找到最短路的点（下面称黑点）和尚未找到最短路的点（下面称白点）。
在所有白点中。找到距离起点 s 最近的点 cur 并染成黑色，vis[cur]=1。
以 cur 为中转点，松弛 cur 的邻接点 y。 4. 重复步骤 2、步骤 3，直到所有点染成黑色。
时间复杂度 O(N^2)

优化策略
### 堆优化必用知识点——重载运算符（overload） #### 定义是指将加减乘除等运算符修改为自定义的含义 #### 标程 ```cpp struct Node { int y; long double val; bool operator<(const Node &b)const { return val>b.val; } }; ``` ### 优化后Dijkstra时间复杂度 $O(m \log_{2}n)
Dijkstra 与 BFS 的关系

BFS 是边权为 1 的 dijkstra。

注意事项
不能用于正负边权混杂的图。
正权不能跑最长路。
注意避免松弛操作溢出，#define int long long。

多次调用 dijkstra 要重置 vis[] 和 dis[]。

标程（弱化版）

#include<bits/stdc++.h> 
#define int long long 
using namespace std; 
const int N=1e4+5, M=1e5+5; 
int dis[N], n, m, s; bool vis[N]; 
struct node 
{ 
int y, val; 
}; 
vector<node> nbr[N]; 
void dijkstra() 
{ 
for(int i=1;i<=n;i++)
{ 
dis[i]=2147483647;
} 
dis[s]=0;
for(int i=1;i<=n;i++) 
{ 
int mini=1e18, id; 
for(int j=1;j<=n;j++) 
{ 
  if(mini>dis[j]&&!vis[j]) 
  { 
    id=j;
    mini=dis[j];
  } 
} 
vis[id]=1; 
for(auto nxt:nbr[id]) 
{ 
 int y=nxt.y, val=nxt.val; 
 if(dis[id]+val<dis[y]) 
 { 
   dis[y]=dis[id]+val;
 } 
} 
} 
} 
signed main() 
{ 
cin>>n>>m>>s; 
for(int i=1;i<=m;i++) 
{ 
int x, y, w; 
cin>>x>>y>>w; 
nbr[x].push_back({y,w}); 
} 
dis[s]=0; 
dijkstra(); 
for(int i=1;i<=n;i++) 
{ 
cout<<dis[i]<<" "; 
} 
}

标程（堆优化版）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+5;
int n,m,dis[N],s;
bool vis[N];
struct node
{
int y,w;
};
vector<node> nbr[N];
void spfa()
{
for(int i=1;i<=n;i++)
{

    dis[i]=2147483647;
}
dis[s]=0;
queue<int> q;
q.push(s);
vis[s]=true;
while(q.empty()==false)
{
    int cur=q.front();
    q.pop();
    vis[cur]=false;
    for(int i=0;i<nbr[cur].size();i++)
    {
        int nxt=nbr[cur][i].y,w=nbr[cur][i].w;
        if(dis[cur]+w<dis[nxt])
        {
            dis[nxt]=dis[cur]+w;
            if(vis[nxt]==false)
            {
                vis[nxt]=true;
                q.push(nxt);
            }
        }
    }
}
}
signed main()
{
cin>>n>>m>>s;
for(int i=1;i<=m;i++)
{
    int u,v,w;
    cin>>u>>v>>w;
    nbr[u].push_back((node){v,w});
}
spfa();
for(int i=1;i<=n;i++)
    cout<<dis[i]<<" ";
return 0;
}

例题1——P1339

题目大意

有一个 n 个点 m 条边的无向图，请求出从 s 到 t 的最短路长度。

样例输入 #1

7 11 5 4 2 4 2 1 4 3 7 2 2 3 4 3 5 7 5 7 3 3 6 1 1 6 3 4 2 4 3 5 6 3 7 2 1

样例输出 #1

Floyd——80 pts 做法

就一模板。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, dis[2505][2505], t, s;
signed main()
{
cin>>n>>m>>s>>t;
for(int i=1;i<=2500;i++)
{
    for(int j=1;j<=2500;j++)
    {
        dis[i][j]=1e9;
    }
}
for(int i=1;i<=m;i++)
{
    int x, y, w;
    cin>>x>>y>>w;
    dis[x][y]=dis[y][x]=w;
}
for(int i=1;i<=n;i++)
{
    dis[i][i]=0;
}
for(int k=1;k<=n;k++)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(dis[i][k]==1000000000||dis[k][j]==1000000000)
            {
                continue;
            }
            dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
        }
    }
}
cout<<dis[s][t];
}

dijkstra——100 pts 做法

也就一模板，注意是无向图。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, s, t;
struct node
{
int y, val;
};
vector<node> nbr[2505];
int dis[2505];
bool vis[2505];
struct Node
{
int y, val;
bool operator<(const Node &b)const
{
    return val>b.val;
} 
};
void dijkstra()
{
memset(vis,0,sizeof vis);
priority_queue<Node> q;
for(int i=1;i<=n;i++)
{
    dis[i]=2147483647;
}
q.push((Node){s,0});
dis[s]=0;
while(!q.empty())
{
    Node now=q.top();
    q.pop();
    int cur=now.y;
    if(vis[cur])
    {
        continue;
    }
    vis[cur]=1;
    for(auto nxt:nbr[cur])
    {
        int y=nxt.y, val=nxt.val;
        if(dis[cur]+val<dis[y])
        {
            dis[y]=dis[cur]+val;
            q.push((Node){y,dis[y]});
        }
    }
} 
}
signed main()
{
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)
{
    int x, y, w;
    cin>>x>>y>>w;
    nbr[x].push_back((node){y,w});
    nbr[y].push_back((node){x,w});
}
dis[s]=0;
dijkstra();
cout<<dis[t];
}

例题2——P1629

题目大意

有一个邮递员要送东西，邮局在节点 1。他总共要送 n-1 样东西，其目的地分别是节点 2 到节点 n。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 m 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 n-1 样东西并且最终回到邮局最少需要的时间。

样例输入 #1

5 10 2 3 5 1 5 5 3 5 6 1 2 8 1 3 8 5 3 4 4 1 8 4 5 3 3 5 6 5 4 2

样例输出 #1

分析

很明显，求起点到各个点的最短路，一遍是求起点到各个点最短路和，另一遍求各个点返回起点最短路和，跑两遍 Dijkstra。建反图，两次 Dijkstra 之间要清空。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5, M=1e5+5;
int dis[N], n, m, s;
bool vis[N];
struct node
{
    int y, val;
};
struct Node
{
    int y, val;
    bool operator<(const Node &b)const
    {
        return val>b.val;
    }
};
vector<node> nbr[N];
void dijkstra()
{

    memset(vis,0,sizeof vis);
    priority_queue<Node> q;

    for(int i=1;i<=n*2;i++)
    {
        dis[i]=2147483647;
    }
    q.push((Node){s,0});
    dis[s]=0;
    while(!q.empty())
    {
        Node now=q.top();
        q.pop();
        int cur=now.y;
        if(vis[cur])
        {
            continue;
        }
        vis[cur]=1;
        for(auto nxt:nbr[cur])
        {
            int y=nxt.y, val=nxt.val;
            if(dis[cur]+val<dis[y])
            {
                dis[y]=dis[cur]+val;
                q.push((Node){y,dis[y]});
            }
        }
    }

}
int t;
signed main(void)
{
    int cnt=0;
    cin>>n>>m;
    s=1;
    for(int i=1;i<=m;i++)
    {
        int x, y, w;
        cin>>x>>y>>w;
        nbr[x].push_back({y,w});
        nbr[y+n].push_back({x+n,w});
    }
    dis[s]=0;
    dijkstra();
    for(int i=2;i<=n;i++)
    {
        cnt+=dis[i];
    }
    s=n+1;
    dis[s]=0;
    dijkstra();
    for(int i=2+n;i<=n+n;i++)
    {
        cnt+=dis[i];
    }
    cout<<cnt;
}

拓展提升 P1346 P1576

P1576关键代码——Dijkstra

memset(vis,0,sizeof vis);
    dis[s]=100.0;
    q.push(s);
    vis[s]=1;
    while(!q.empty())
    {
        int cur=q.front();
        q.pop();
        vis[cur]=0;
        for(auto qq:nbr[cur])
        {
            int nxt=qq.y;
            double w=qq.w;
            if(dis[cur]/w<dis[nxt])
            {
                dis[nxt]=dis[cur]/w;
                if(!vis[nxt])
                {
                    vis[nxt]=1;
                    q.push(nxt);
                }
            }
        }
    }

Bellman-Ford 算法

概述

Bellman-Ford 算法是由理查德·贝尔曼（Richard Bellman）和莱斯特·福特创立的，求解单源最短路径问题的一种算法。

有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。

它的原理是对图进行 m-1 次松弛操作，得到所有可能的最短路径。

其优于 Dijkstra 算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达 O(n \times m)。但算法可以进行若干种优化，提高了效率。

实现

双重循环枚举，和暴力差不多。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
    int x, y, w;
}e[2000005];
int n, m, s;
int dis[200005];
void bellman_ford()
{
    for(int i=1;i<=n;i++)
    {
        dis[i]=2147483647;
    }
    dis[s]=0;
    for(int t=1;t<n;t++)
    {
        for(int i=1;i<=m;i++)
        {
            if(dis[e[i].x]+e[i].w<dis[e[i].y])
            {
                dis[e[i].y]=dis[e[i].x]+e[i].w;
            }
        }
    }
}
signed main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        cin>>e[i].x>>e[i].y>>e[i].w;
    }
    bellman_ford();
    for(int i=1;i<=n;i++)
    {
        cout<<dis[i]<<" ";
    }
}

SPFA 算法

死了的算法。

理论上对 Bellman-Ford 算法进行优化，但这种优化被证实可卡掉的。

用队列进行松弛。

除了队列优化（SPFA）之外，Bellman–Ford 还有其他形式的优化，这些优化在部分图上效果明显，但在某些特殊图上，最坏复杂度可能达到指数级。

堆优化：将队列换成堆，与 Dijkstra 的区别是允许一个点多次入队。在有负权边的图可能被卡成指数级复杂度。
栈优化：将队列换成栈（即将原来的 BFS 过程变成 DFS），在寻找负环时可能具有更高效率，但最坏时间复杂度仍然为指数级。
LLL 优化：将普通队列换成双端队列，每次将入队结点距离和队内距离平均值比较，如果更大则插入至队尾，否则插入队首。
SLF 优化：将普通队列换成双端队列，每次将入队结点距离和队首比较，如果更大则插入至队尾，否则插入队首。
D´Esopo–Pape 算法：将普通队列换成双端队列，如果一个节点之前没有入队，则将其插入队尾，否则插入队首。

上述“其他优化”来自 OI-WIKI

但一句话总结，都会被卡。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+5;
int t, n, m;
struct node
{
    int y, w;
};
vector<node> nbr[N];
int cnt[N], dis[N];
bool vis[N];
void spfa()
{
    memset(cnt,0,sizeof cnt);
    memset(vis,0,sizeof vis);
    memset(dis,0x3f,sizeof dis);
    queue<int> q;
    q.push(1);
    vis[1]=1;
    while(!q.empty())
    {
        int cur=q.front();
        q.pop();
        vis[cur]=0;
        for(auto qq:nbr[cur])
        {
            int nxt=qq.y, val=qq.w;
            if(dis[cur]+val<dis[nxt])
            {
                dis[nxt]=dis[cur]+val;
                cnt[nxt]=cnt[cur]+1;
                if(cnt[nxt]>n-1)
                {
                    cout<<"YES\n";
                    return ;
                }
                q.push(nxt);
            }
        }
    }
    cout<<"NO\n";
    return ;
}
signed main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            nbr[i].clear();
        } 
        for(int i=1;i<=m;i++)
        {
            int x, y, w;
            cin>>x>>y>>w;
            if(w>=0)
            {
                nbr[y].push_back((node){x,w});
            }
            nbr[x].push_back((node){y,w});
        }
        spfa();
    }
}

我们用队列来维护哪些结点可能会引起松弛操作，就能避免访问不必要的边。

这个算法已经死了就不多赘述了。

换根树形DP（二次扫描DP）

作用

当不同结点作为根结点时，状态转移的结果不一样，若枚举每个点作为根结点再DP，时间复杂度会很高。

这种情况下，使用换根DP处理相邻两个结点之间的贡献，达到快速换根的效果。

使用场景

对于一棵树，寻找以某个点 cur 为根结点取得的最大值或最小值或方案数。

实现步骤

任选 1 点作为根结点（比如结点 1），跑一遍树形 DP，得到 dp_i 表示以 i 为根结点的子树的 XXX 的最大值或最小值或方案数。
从根结点（上述中我们用 1 来举例）再次 DFS 遍历，从父结点到子结点转移得到 f_i。

例题

Ⅰ：P3478 POI 2008 STA-station

很板的一道换根 DP 题。

分析

定义 dp_cur 表示以 cur 为根的子树的结点的全局（以固定点为根结点）深度之和。转移很好想：dp_{cur}+=dp_{nxt}。
初始状态：dp_{cur}=dep_{cur}，其中 dep_{cur} 表示 cur 结点的深度。
定义 f_i 表示以 i 为全局根结点的结点深度之和。很显然答案输出 f_i 的值最大的 i。
考虑从上往下的转移，如从 cur 遍历子结点到 nxt。
虽然这题可以省略，但为了养成好习惯，f_1=dp_1。
记得开 long long。

区间 DP

定义

对于一个序列，以区间为子问题的一类DP问题

常见状态

## 此类问题的特征 1. 从左往右推，从右往左推会有不同的效果。 2. 区间 DP 通常是合并/拆分类问题。 3. 区间 DP 可以处理两端类问题。 4. 状态转移方程要么枚举中间断点，要么枚举两个端点。 ## 经典例题 ### First：[P1622](/problem/P1622) 将 $Q$ 个囚犯释放后， $p$ 个牢房分成了 $Q+L$ 段。逆向思考，将题意转化为抓 $Q$ 人进去，每抓一个人进去，能说上话的囚犯就发肉吃。可以将题目看作另一个版本的石子合并，变为“将 $Q+1$ 堆石子合并，每次插入一个元素就将相邻石子堆合并，代价为石子数量之和。”此时求最小代价即可。 ```cpp for(int len=1;len<=q;len++) { for(int i=1;i+len-1<=q;i++) { int j=i+len-1; dp[i][j]=1e18; for(int k=i;k<=j;k++) { dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+a[j+1]-a[i-1]-2); } } } ``` 上面是核心代码。注意事项：$a_{q+1}=p+1$。 ### Second：[P2858](/problem/P2858) 定义状态为 $dp_{i,j}$ 表示卖掉区间 $[i,j]$ 的零食获得的最大收益。此时答案为 $dp_{1,n}$。状态转移方程：$dp_{i,j}=max(dp_{i,j-1}+v_j \times (n-len+1),dp_{i+1,j}+v_i \times (n-len+1))

初始状态：dp_{i,i}=v_i \times n。

Third：P4290

发现字符串总由短拓展到长，考虑区间 DP。

定义状态 dp_{i.j} 表示区间 [i.j] 的子串能否由 W、I、N、G 演变而来。

答案：if(dp[1][n][0])cout<<'W';.....。

（其他字符的情况以此类推）

状态转移是 ex 小分讨就不放代码了（怕有人贺）。

Fourth：P8675

P8675 1.积木不能悬空，同一行不能间断，考虑从下往上递推;

2.同一行必须连续，考虑枚举区间起点和终点;

3.状态: dp[L][i][j] 表示第 L 层在区间 i 到 j 搭积木的方案数。

4.答案: (sigma(dp[L][i][j])+ 1) % mod;

5.转移:

for(int i= 1;i <= m; i++)
  for(int j=i; j <= m; j++)
    for(int ii = 1; ii <= i; ii++)
      for(int jj=j; jj<=m;jj++)
        if(vis[L][j] - vis[L][i-1]== 0)//i到i没有障碍物
          dp[L][i][j]=(dp[L][i][j] + dp[L-1][ii][jj]) % mod;

初始: dp[0][1][m]=1

7.时间 O(n^5)

8.利用二维前缀和sum[i][j]维护以(i,j)端点时dp[][]的区间和，加速枚举

试炼场

P1220 关路灯
CF1114D

分块

定义

是一种分治思想，通常指的是序列分块。对于区间修改和区间询问总是分成左端不完整的块、中间完整的块、右端不完整的块三个部分处理

与线段树的区别

使用范围更广泛，但时间复杂度更高。

修改操作

维护一个区间标记 tag_i，表示第 i 个块的修改值。

分情况讨论：

区间 [L,R] 在同一块中，暴力修改 a 数组以及原块的信息 sum 数组。
区间 [L,R] 不在同一块中，分成三部分： ①. 左端不完整的块和右端不完整的块，参照情况 1 暴力。 ②. 中间完整的块，tag_i+=val

带修改询问

情况1：询问区间 [L,R] 在一个块中，暴力枚举 a_i 和 tag 数组。

情况2：区间 [L,R] 不在同一块中，分为三个部分：

左端和右端不完整的块参照情况 1。
中间完整的块要处理 sum_i 和 tag_i。

模板代码

线段树1分块版

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int a[N];
int L[N], R[N], pos[N], n, m, t, tag[N], sum[N];
void update(int lt, int rt, int val)
{
int x=pos[lt], y=pos[rt];
if(x==y)
{
    for(int i=lt;i<=rt;i++)
    {
        a[i]+=val;
        sum[x]+=val;
    }
}
else
{
    for(int i=x+1;i<=y-1;i++)
    {
        tag[i]+=val;
    }
    for(int i=lt;i<=R[x];i++)
    {
        a[i]+=val, sum[x]+=val;
    }
    for(int i=L[y];i<=rt;i++)
    {
        a[i]+=val;
        sum[y]+=val;
    }
}
return ;
}
int query(int lt, int rt)
{
int x=pos[lt], y=pos[rt];
int ans=0;
if(x==y)
{
    for(int i=lt;i<=rt;i++)
    {
        ans+=a[i];
    }
}
else
{
    for(int i=x+1;i<=y-1;i++)
    {
        ans+=sum[i]+tag[i]*(R[i]-L[i]+1);
    } 
    for(int i=lt;i<=R[x];i++)
    {
        ans+=a[i]+tag[x];
    }
    for(int i=L[y];i<=rt;i++)
    {
        ans+=a[i]+tag[y];
    }
}
return ans;
}
signed main()
{
cin>>m;
cin>>n;
for(int i=1;i<=m;i++)
{
    cin>>a[i];
}
t=sqrt(m);
for(int i=1;i<=t;i++)
{
    L[i]=(i-1)*t+1;
    R[i]=i*t;
}
if(R[t]<m)
{
    t++;
    L[t]=R[t-1]+1;
    R[t]=m;
}
for(int i=1;i<=t;i++)
{
    for(int j=L[i];j<=R[i];j++)
    {
        pos[j]=i;
        sum[i]+=a[j];
    }
}
for(int i=1;i<=n;i++)
{
    int opt;
    cin>>opt;
    if(opt==1)
    {
        int x, y, k;
        cin>>x>>y>>k;
        update(x,y,k);
    }
    else
    {
        int x, y;
        cin>>x>>y;
        cout<<query(x,y)<<"\n";
    }
}
}

线段树2就不放了。

例题

First：LOJ6278

询问：单独一块时暴力。否则不完整的块暴力，完整的块二分。

每次需要高频率还原 num 动态数组。

还原函数：

void resort(int x)
{
    num[x].clear();
    for(int i=L[x];i<=R[x];i++)
    {
        num[x].push_back(a[i]);
    }
    sort(num[x].begin(), num[x].end());
}

RMQ(Range Maximum/Minimum Query)

定义

指的是在一个序列中多次进行静态区间求最值。

算法原理

倍增思想。

实现

分为两部分：预处理和询问（S 组算法里最长的预处理）。

first part：预处理

维护 dp_{i,j} 表示以下标 i 为起点，跨度为 2^j 的最大值。

状态转移：dp_{i,j}=\max(dp_{i,j-1},dp_{i+2^{j-1},j-1})

初始状态：dp_{i,0}=a_i。

维护 lg_i 表示 i 取以 2 为底的对数向下取整。lg_i=-1，lg_i=lg_{i>>1}+1。

second part：询问

对于 [l,r] 的询问，一定能找到 2 的幂超过 r-l+1 的一半。

求覆盖区间一半以上的幂，p=lg_{r-l+1}。

### 代码 ```cpp #include<bits/stdc++.h> #define int long long using namespace std; int dp[100005][20], a[100005], n, m, lg[100005]; void init() { lg[0]=-1; for(int i=1;i<=n;i++) { dp[i][0]=a[i]; lg[i]=lg[i>>1]+1; } for(int j=1;(1<<j)<=n;j++) { for(int i=1;i+(1<<j)-1<=n;i++) { dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]); } } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; } init(); while(m--) { int l, r; cin>>l>>r; int mi=lg[r-l+1]; cout<<max(dp[l][mi],dp[r-(1<<mi)+1][mi])<<"\n"; } } ``` ## 例题 ### First：[P2048 超级钢琴](/problem/P2048) 温馨提示：本题不适合初学者阅读并尝试，同时我不会放代码（因为紫题）。 #### 题意给定 $n$ 个元素，选 $k$ 个不完全重复区间，区间长度在 $[L,R]$ 内，求 $k$ 次选取区间和所得的最大值。 #### 先考虑简化版 k=1 时维护 $sum_i$ 表示前缀和。维护 $dp_{i,j}$ 表示以 $i$ 为起点跨度为 $2^j$ 的区间内最大的前缀和。循环枚举区间起点 $i$，在 $[i+L-1,\min(n,i+R-1)]$ 询问最大前缀和，维护 $\max(sum_i-sum_{i-1})

分析

现在来考虑 k \le 500000 的情况。

考虑优先队列维护前 k 大的区间和，问题是起点 j 贡献的区间可能不止一个。

维护 pos_{i,j} 表示 dp_{i,j} 在序列中所在的下标，pos_{i,0}=i。

当 dp_{i,j-1} > dp_{i+2^{j-1},j-1} 时，pos_{i,j}=pos_{i,j-1}。

否则，pos_{i,j}=pos_{i+2^{j-1},j-1}。

对于以 i 为起点的最大区间和，可借助 pos 数组找到终点 j，然后在区间 [i+L-1,j-1] 和区间 [j+1,i+R-1] 内再次寻找 2 个最大区间和对应的 j1,j2，插入优先队列。

循环从优先队列中取 k 个区间，每取 1 次，将被取出的区间终点 j 一分为二，重复 k 次，最后求和即为答案。

状态压缩DP

含义

是一种对状态表示形式的一种优化。

前置知识——常见的位操作

任何二进制数位；

&1 得到它本身。
^1 则取反。
&0 则赋值为 0。
|1 则赋值为 1。

通常二进制的第一位我们称之为第零位。

(n>>k)&1 取出二进制下 n 的第 k 位（从右往左数）。
n&((1<<k)-1) 去除二进制下 n 的右 k 位。
n^(1<<k) 将二进制下 n 的第 k 位取反。
n|(1<<k) 将二进制下 n 的第 k 位赋值为 1。
n&(~(1<<k)) 将二进制下 n 的第 k 位赋值为 0。

模板例题——P10447 最短 Hamilton 路径

见 https://www.luogu.com.cn/article/z883dedy。

前置知识——常用优先级

四则运算符 > 位移运算符 > 位运算符 > 逻辑运算符。

例题

First：P1879

定义状态 dp_{i,j} 表示前 i 行且第 i 行的种草状态为二进制下的 j 的方案数。

答案为所有 dp_{m,j} 的和对 100000000 取模。

维护 soil_i 表示第 i 行的肥沃情况。当种草状态 j \& soil_i = j，种草在肥沃土地上。

上下中草的两个状态按位与的结果为 0 时，不冲突。

种草状态 i 左移 1 位后再和 i 按位与的结果为 0 时，不冲突。

初始状态：dp_{0,0}=1

状态转移除了判肥沃以外还是有点板的。

Second：P2704 炮兵阵地

定义状态为 dp_{i,j,k} 表示前 i 行且第 i 行状态为二进制下的 j，第 i-1 行的状态为二进制下的 k 的最大炮兵数。

答案即为 dp_{n,j,k} 的最大值。

状态转移稍有点ex。

提示：需要维护一个 soil_i，soil[i]=(soil[i]<<1)+(c=='P');。

初始状态：dp_{0,0}=0，其余极小值。

优化：滚动数组、提前筛可能状态。

Third：P5911

状态：dp_i 表示 n 个人过桥的状态为二进制下的 i 时的最小时间。
答案：dp_{2^{n}-1}。
预处理辅助状态：w_i 表示二进制下的 i 时的人的体重之和，t_i 表示最慢的人的时间。
枚举二进制状态 i 的所有子集的方法： for(int j=i;j!=0;j=(j-1)&i;
LCA（Lowest Common Ancestor）

定义

在树上取两点 x,y，他们的 LCA 为距离他们最近的公共祖先。

本章主要讲的是倍增求 LCA。

暴力求取

从 x 开始向上移动到根结点，并标记沿途结点。
从 y 开始向上移动到根结点，第一个被标记的就是 x 和 y 的 LCA。

倍增求 LCA

从任意点对 (x,y) 移到 x 和 y 的 LCA 的距离可拆分为 2 的幂的和。

若预处理任意点 x 移动 2 的幂步所到达的结点编号，则不超过 \log_2{n} 次即可找到 LCA。

具体实现

first：预处理倍增 DP

定义状态 dp_{i,j} 表示点 i 向上移动 2^j 步到达的结点编号。

状态转移方程：枚举 j 从 1 到 \log_2 n，dp_{i,j}=dp_{dp_{i,j-1},j-1}。

初始状态：dp_{i,0}=fa_i。

代码片段

void pre_lca(int cur, int fa)
{
    dep[cur]=dep[fa]+1;
    dp[cur][0]=fa;
    for(int i=1;(1<<i)<=dep[cur];i++)
    {
        dp[cur][i]=dp[dp[cur][i-1]][i-1];
    }
    for(int nxt:nbr[cur])
    {
        if(nxt!=fa)pre_lca(nxt,cur);
    }
}

second：处理单次询问

第一步：约定深度较大的点，若 dep_x>dep_y，交换 x 和 y。

第二步：将深度较大的结点 y 倍增向上跳至深度等于 x。

第三步：判断 x 是否等于 y。若已经相等则 x 为 LCA，停止寻找。

第四步：x 和 y 一起倍增向上跳，只要 x 和 y 不重合。

第五步：x 向上一步即为 LCA。

代码片段

int lca(int x, int y)
{
    if(dep[y]<dep[x])swap(x,y);
    for(int i=20;i>-1;i--)
    {
        if(dep[dp[y][i]]>=dep[x])
        {
            y=dp[y][i];
        }
    }
    if(x==y)return x;
    for(int i=20;i>-1;i--)
    {
        if(dp[x][i]!=dp[y][i])
        {
            x=dp[x][i],y=dp[y][i];
        }
    }
    return dp[x][0];
}

时间复杂度

预处理是 O(n \log_2 n) 的，中间单次求取仅为 O(n)

模板代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[500005][21],dep[500005], n, m, s;
vector<int> nbr[500005];
void pre_lca(int cur, int fa)
{
    dep[cur]=dep[fa]+1;
    dp[cur][0]=fa;
    for(int i=1;(1<<i)<=dep[cur];i++)
    {
        dp[cur][i]=dp[dp[cur][i-1]][i-1];
    }
    for(int nxt:nbr[cur])
    {
        if(nxt!=fa)pre_lca(nxt,cur);
    }
}
int lca(int x, int y)
{
    if(dep[y]<dep[x])swap(x,y);
    for(int i=20;i>-1;i--)
    {
        if(dep[dp[y][i]]>=dep[x])
        {
            y=dp[y][i];
        }
    }
    if(x==y)return x;
    for(int i=20;i>-1;i--)
    {
        if(dp[x][i]!=dp[y][i])
        {
            x=dp[x][i],y=dp[y][i];
        }
    }
    return dp[x][0];
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m>>s;
    for(int i=1;i<n;i++)
    {
        int x, y;
        cin>>x>>y;
        nbr[x].push_back(y);
        nbr[y].push_back(x);
    }
    pre_lca(s,0);
    for(int i=1;i<=m;i++)
    {
        int x, y;
        cin>>x>>y;
        cout<<lca(x,y)<<"\n";
    }
}

LCA 应用

求树上两点之间距离。
树上差分。

LCA 求树上两点之间距离

维护 dis_x 表示根结点到 x 的距离。

## LCA 例题 ### first：[P5836](/problem/P5836) #### 方法 1 点权可以转为 $0$ 或 $1$，维护 $dis_i$ 表示由根结点到 $i$ 的距离。维护深度 $dep_i$，对于每次询问，若 `(dis[a]+dis[b]-2*dis[lcad]+w[lcad]==dep[a]+dep[b]-2*dep[lcad]+1)&&c!='H'` 或 `dis[a]+dis[b]-2*dis[lcad]+w[lcad]==0&&c=='H'` 则输出 $0$，否则输出 $1$。 #### 方法 2 若一条边的两个端点的 $w$ 相同，则 `unionn` 这两个端点。若一条路径上点权相同，则两个端点一定在同一集合。若该集合的权值不等于询问，输出 $0$，否则输出 $1$。 ```cpp while(m--) { int x, y; char c; cin>>x>>y>>c; if(c=='H') { cout<<!(find(x)==find(y)&&w[x]==0); } else { cout<<!(find(x)==find(y)&&w[x]==1); } } ``` #### 方法 3 维护 $dp_{i,j}$ 表示 $i$ 向上动 $2^j$ 步到达的结点编号，维护 $yes_{i,j,0/1}$ 表示 $i$ 向上跳 $2^j$ 步是否有 $w$ 为 $0/1$ 的点。 `yes[cur][i][0]=yes[cur][i-1][0]|yes[dp[cur][i-1]][i-1][0],yes[cur][i][1]=yes[cur][i-1][1]|yes[dp[cur][i-1]][i-1][1];`。初始状态：$dp_{i,0}=fa_i$，$yes_{i,0,w_{fa}}=1$。 ### second：[CF519E](https://codeforces.com/problemset/problem/519/E) 若 $A$ 到 $B$ 的距离为奇数，则答案直接为 $0$。否则分情况讨论： 1. 中间位置的点 $x=lca

$x$ 儿子结点中包含 $A$ 和 $B$ 的子树剔除，其余为答案。

中间位置的点 x 不是 lca

约定深度较大的点为 B，找到 B 向上距离 x 一步的点 p，则答案为 size_x-size_p。

注意特殊情况：A==B 时，答案为 n。

从 lca 到 x 的距离为 \frac{dep_B-dep_A}{2}。

void work(int x,int y)
{
    if(x==y)
    {
        cout<<n<<"\n";
        return ;
    }
    if(dep[x]==dep[y])
    {
        for(int i=14;i>=0;i--)
        {
            if(dp[x][i]!=dp[y][i])
            {
                x=dp[x][i],y=dp[y][i];
            }
        }
        cout<<size[1]-size[x]-size[y]<<"\n";
        return  ;
    }
    if(dep[x]<dep[y]) swap(x,y);
    if((dep[x]-dep[y])%2==1)
    {
        cout<<"0\n";
        return ;
    }
    int x2=x,len=(dep[x]-dep[y])/2;
    for(int i=14;i>=0;i--)
    {
        if(dep[dp[x][i]]>=dep[y])
        {
            x=dp[x][i];
        }
    }
    if(x==y)
    {
        len+=dep[x];
        for(int i=14;i>=0;i--)
        {
            if(dep[dp[x2][i]]>len)
            {
                x2=dp[x2][i];
            }
        }
        cout<<size[dp[x2][0]]-size[x2]<<"\n";
        return ;
    }
    for(int i=14;i>=0;i--)
    {
        if(dp[x][i]!=dp[y][i])
        {
            x=dp[x][i],y=dp[y][i];
        }
    }
    len+=dep[x]-1;
    for(int i=14;i>=0;i--)
    {
        if(dep[dp[x2][i]]>len)
        {
            x2=dp[x2][i];
        }
    }
    cout<<size[dp[x2][0]]-size[x2]<<"\n";
}

Third：P8972 一切都已过去

见 https://www.luogu.com.cn/article/58jlmt7i

方便阅读搬过来。

从数据范围很容易发现，如果我们把边权累乘再判整数，炸掉是必然的，这时候，我们来发现一个性质：只有小数部分有 2 和 5 相乘的时候，才可能变成整数。当然，这并不是绝对的，例如 2.02 \times 5 就不是整数。从上面举的例子很容易发现一个性质：两个实数的乘积是否为整数与小数点数位也有关系。一对 2 和 5 可以抵消掉一个小数点数位（2 和 5 可以在任意且不同数位上，并且 2 和 5 的倍数也有用）。这时，我们可以将边权通过不断 \times 10 变成整数，并分解质因数分别求因数中 2 和 5 的个数（点权也要处理）。2 和 5 的个数求出来了，小数点数位也很好处理。最终的小数点位数应该是所有路径上的边权小数点位数之和，所以我们在将边权化整数时再维护一个变量统计小数点位数并记录到邻接矩阵里。若路径 x 到 y 的总边权乘上 x 的点权得到的结果中 2 的个数和 5 的个数大于或等于总小数点位数，则其为整数。分别维护即可。

注意：若边权或点权为 0 则对应维护的当前点权或点权的 2 和 5 赋予极大值。

树状数组

功能

区间查询
单点修改
原理

用一个树上结点维护序列 [i,j] 的元素之和。

$\texttt{lowbit}$ 的求取也很简单，就是 $x&-x$。 ## 模板代码 ```cpp int n, m, tree[1000005]; int lowbit(int x) { return x&-x; } int query(int x) { int sum=0; while(x!=0) { sum+=tree[x]; x-=lowbit(x); } return sum; } void update(int x, int val) { while(x<=n) { tree[x]+=val; x+=lowbit(x); } return ; } ``` # 背包 ## 例题：[ABC118D](/problem/AT_abc118_d) 1. 数位越多越好 2. 把木棍数量 $n$ 当作容量，数码当作物品，数码使用的木棍数当作重量，价值是数位，都是 $1$。 3. 转化为完全背包问题求最大价值 4. 输出结果有两种策略，一是记录决策点，二是贪心选木棍少且数码大的。 ## 例题：[P1450](/problem/P1450) 1. 多重背包，每种物品的个数大于1，且不是无限; 2. 求背包恰好放满 $s$ 的方案数; 3. 将 $s$ 视为容量，将面值视为重量; ### 方法 1：多重背包求方案数 ```cpp for(int i=1;i<=4;i++) for(int j=s;j>=0;j--)//将多重背包转化为01背包 for(int k=0;k<=d[i];k++) if(j>=k*c[i]) dp[j]=dp[j]+dp[j-k*c[i]]; ``` 明显时间复杂度爆炸，~~初赛跑到复赛都跑不完~~。 ### 方法 2：容斥原理+状压 4. 多重背包的方案数是完全背包方案数的一部分; 5. 完全背包时间复杂度较低，考虑容斥，减去不合法的方案数， 6. 对于第 $i$ 种物品，凡是选择超过 $d_i$ 的都是不合法的; 7. 对于第 $1$ 种物品，在背包中先放入 $d[1]+1$ 个，那么剩余的空间 $s-c[1]*(d[1]+1)$ 无论怎么放都不合法 8. 根据容斥原理，答案=总方案数- $1$ 种物品放超+ $2$ 种物品放超- $3$ 种物品放超+ $4$ 种物品放超; 9. 将 $4$ 种物品状压，$0$ 表示合法，$1$ 表示不合法，总共有 $16$ 种组合，枚举并贡献答案; # IDDFS迭代加深搜索 ## 使用场景搜索树非常大而深度答案深度浅，一般在 $20$ 以内，且使用深度优先搜索会超时，使用广度优先搜索会超空间。 ## 算法原理 1. 以 DFS 的形式搜索。 2. 设定搜索的深度限制 $limit$。 3. 深度优先搜索不能超过 $limit$。且要恰好遍历所有 $limit$ 的状态。 4. 若在 $limit$ 层未找到答案，`limit++;`，重新 DFS。 ## 搜索优化 1. 最优性剪枝 2. 可行性剪枝 3. 排除重复状态 4. 调整搜索顺序 ## 例题：[POJ-3134](https://www.vjudge.net/problem/POJ-3134) 本质上是指数从 $1$ 开始，可以做加减法，求最快到达$n$ 的次数。每次只能选已经求出的中间指数求和或者做差，可选多次。 ## 例题：[P10489](/problem/P10489) https://www.luogu.com/article/x8dwns50 放个友情链接。 # IDA* 启发式迭代加深搜索 IDDFS 和估价函数做可行性剪枝的融合 ## 例题：[P2324](/problem/P2324) 将搜索的过程视为空格移动的过程。维护二维数组 $a_{i,j}$ 表示棋盘的状态，每次移动 swap 即可更新。每次搜索枚举至多 $8$ 个方向。每一步至多还原 $1$ 个棋子，最后一步至多还原两个棋子。估价函数：统计当前棋盘和目标棋盘的不同位置个数 $cnt$，若 $cnt>dep-cur+1$，则剪枝。 ## 例题：[P10488](/problem/P10488) 每次操作只有至多三本书的相对位置发生变化。设计估价函数：比较当前状态与终止状态的差异，若超过 $3\times (dep-cur)$，则剪枝。 ## 例题：[UVA1505](/problem/UVA1505) 估价函数：统计当前矩阵内的颜色数量 $cnt$，若 $cnt-1>dep-cur$，则剪枝。更新：设操作颜色为 $c$，则与当前左上角连通块接壤的颜色为 $c$ 的格子被拓展。 # 题目part P2217 1. n-1次分割后一定的到n个矩阵; 2. 根据均方差的公式，最后的答案最小等价于![](https://s21.ax1x.com/2024/10/12/pAY5v9J.png)最小; 其中xi指的是每个矩阵的元素和，x'是n个矩阵元素和的平均值; 3. 每切一次，都是在当前矩阵内进行分割，可以视为子问题的划分，考虑DP; 4. 状态：dp[x1][y1][x2][y2][k] 表示以(x1,y1)为左上角，(x2,y2)为右下角的矩阵切 k 次的最小价值 5. 答案 `sqrt(dp[1][1][a][b][n]/n)` 6. 状态转移: `dp[x1][y1][x2][y2][k]= min(,dp[x1][y1][i][y2][p] + dp[i+1][y1][x2][y2][k-p]); ` ` dp[x1][y1][x2][y2][k]= min(, dp[x1][y1][x2][i][p] + dp[x1][i+1][x2][y2][k-p]) ` 7. 初始状态: dp[x1][y1][x2][y2][1]=(元素之和-平均值)^2 8. 可以选择二维前缀和做优化 # 点双连通&边双连通 ## 点双连通的概念在无向图中，对于点 $x$ 和点 $y$，删除任意点（不为 $x$ 和 $y$），$x$ 和 $y$ 都连通，那么称 $x$ 和 $y$ 是双连通的。 ## 边双连通的概念在无向图中，对于点 $x$ 和点 $y$，删除任意边（不为 $x$ 和 $y$），$x$ 和 $y$ 都连通，那么称 $x$ 和 $y$ 是双连通的。 ## 性质1 点双连通不具有传递性，但是边双连通具有传递性。 ![](https://s21.ax1x.com/2024/11/03/pAr1HXQ.png) 上图中，$x$ 和 $y$ 为点双连通的，$y$ 和 $z$ 也为双连通的，但是 $x$ 和 $z$ 不为双连通的，因为当把 $y$ 删掉后，$x$ 和 $z$ 不再连通。 # 割点在无向图中，若 $x$ 被删除后，连通块的数量增加，那么 $x$ 就是一个割点。如果一个无向图至少存在 $3$ 个点时，才有可能出现割点。证明：一个点时，按照上面的定义，并不存在割点；两个点时，删掉一个点，剩下的一个点只会有一个连通块，并没有增加。 ## 割点的判定维护 $dfn_x$ 表示在一次 dfs 中点 $x$ 被遍历到的次序，称为时间戳。维护 $low_x$ 表示点 $x$ 在一次 dfs 中能到达的最小时间戳。当 dfs 中从 $x$ 走向 $y$，且 $low_y \ge dfn_x$ 时，$x$ 可能为割点。 ![](https://s21.ax1x.com/2024/11/03/pAr30Bj.png) 为什么说可能呢，如果上图中 $x$ 前的那些点不存在，也就是 $x$ 为 dfs 树的根结点，且 $y$ 为 $x$ 唯一的儿子，则 $x$ 不是割点。 ```cpp void tarjan(int cur) { dfn[cur]=low[cur]=++num; int cnt=0; for(int nxt:nbr[cur]) { if(!dfn[nxt]) { tarjan(nxt); low[cur]=min(low[cur],low[nxt]); cnt++; if(low[nxt]>=dfn[cur]) { if(cur!=root||cnt>=2) { cut[cur]=1; } } } else { low[cur]=min(low[cur],dfn[nxt]); } } return ; } ``` ## 模板题——[P3388 【模板】割点](/problem/P3388) ```cpp #include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+5; int dfn[N],low[N],cut[N],n,m, ans; vector<int> nbr[N]; int root,num; void tarjan(int cur) { dfn[cur]=low[cur]=++num; int cnt=0; for(int nxt:nbr[cur]) { if(!dfn[nxt]) { tarjan(nxt); low[cur]=min(low[cur],low[nxt]); cnt++; if(low[nxt]>=dfn[cur]) { if(cur!=root||cnt>=2) { cut[cur]=1; } } } else { low[cur]=min(low[cur],dfn[nxt]); } } return ; } signed main() { cin>>n>>m; for(int i=1;i<=m;i++) { int x, y; cin>>x>>y; nbr[x].push_back(y); nbr[y].push_back(x); } for(int i=1;i<=n;i++) { if(!dfn[i]) { root=i; tarjan(i); } } for(int i=1;i<=n;i++)if(cut[i])ans++; cout<<ans<<"\n"; for(int i=1;i<=n;i++) { if(cut[i])cout<<i<<" "; } return 0; } ``` ## 练习题——[CF22C](/problem/CF22C) 题意：构造 $n$ 个点，$m$ 条边的无向连通图，且无重边，题中给出的 $v$ 点必须为割点。先考虑无解，~~显然，~~当 $m<n-1$ 时，图无法连通，必然无解。考虑 $n-1$ 条边都与 $v$ 相连构成一棵树，此时图连通且 $v$ 为割点，然后加入多余的边。加边时，确保不能破坏 $v$ 为割点的性质。为保证容纳的边尽量多且不破坏该性质，考虑留一个点不参与连边，剩下的 $n-2$ 个点构造完全图，直到剩余的边用完为止。当然，若最后还有剩余的边，则无解。 # 割边 ## 定义在无向图中，若删除一条边 $e$ 后，连通块数量增加，那么称 $e$ 是一条割边。 ## 性质 1. 割边删除后，连通块数量 $+1$。 2. 割边一定不在环上。 3. 割边通常处理必经边问题。 ## 割边的判定与割点类似。维护 $dfn_x$ 表示在一次 dfs 中点 $x$ 被遍历到的次序，称为时间戳。维护 $low_x$ 表示点 $x$ 在一次 dfs 中能到达的最小时间戳。若 $low_y > dfn_x$，则当前边为割边，其中 $x,y$ 为这条边的两个端点。 ## 模板代码模板题传送门：[割边模板](https://www.luogu.com.cn/problem/T103481) ```cpp #include <bits/stdc++.h> using namespace std; int n,m; int dfn[100005],low[100005],in,res; bool vis[100005],f[100005]; vector<int> e[100005]; int dfs_clock; bool isbridge[100005]; struct nn { int x,y; }d[100005]; vector<int> G[100005]; int cnt_bridge; int fath[100005]; bool cmp(nn xx,nn yy) { if(xx.x==yy.x)return xx.y<yy.y; return xx.x<yy.x; } void tarjan(int u, int fa) { fath[u]=fa; low[u]=dfn[u]=++dfs_clock; vis[u]=true; for(int i=0;i<e[u].size();i++) { int v=e[u][i]; if(!dfn[v]) { tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>dfn[u]) { isbridge[v]=true; ++cnt_bridge; } } else if(dfn[v]<dfn[u]&&v!=fa) { low[u]=min(low[u], dfn[v]); } } } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; e[x].push_back(y),e[y].push_back(x); } for(int i=1;i<=n;i++)if(!vis[i])tarjan(i,i); int num=0; for(int i=1;i<=n;i++)if(isbridge[i]==true)d[++num].x=min(fath[i],i),d[num].y=max(fath[i],i); cout<<num; return 0; }

算法集合&总结

算法·理论

写在最前面

前言

更新日志

目录

线段树 Segment Tree

使用场景

使用思想

详解

算法实现

时间复杂度分析

未优化代码

线段树的优化

优化后代码

带乘法的线段树

代码

例题 https://www.luogu.com.cn/problem/CF240F

分析

权值线段树 Weighted segment tree

概念

作用

例题① —— P1637 三元上升子序列

题目大意

暴力100分思路

暴力100分代码（拒绝抄袭，已将所有代码加入防抄袭）

权值线段树优化

代码（已加防抄袭）

例题②—— P1908 逆序对

题目大意

权值线段树解法

代码（加防抄袭）

树形 DP

含义&分类

第一类树形 DP 超详解

例题①：P1122

简要题意：

分析

First step：状态

Fourth step：初始状态

Fourth step：初始状态

Tarjan 代码

法2——Kosaraju 算法

引入

过程

Kosaraju 代码

法3——Garbow 算法

Garbow 代码

例题：B3609 [图论与代数结构 701] 强连通分量

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

代码+解析注释——Tarjan

强连通分量试炼场

difficult 1

difficult 1 例题详解——P3916

代码

difficult 2

difficult 2 例题详解——P3387

代码

difficult 2 例题详解——P2863

代码

difficult 2 例题详解——P2341

代码

difficult PRO

difficult PRO 例题详解——P1407

分析

difficult PRO 例题详解——P1262

题意

difficult PRO 例题详解——P2746

提炼大意

分析

代码

单调队列

定义

使用场景