# code1

**Repository Path**: YZY00Raiser/code1

## Basic Information

- **Project Name**: code1
- **Description**: 算法学习笔记。。。。。。
- **Primary Language**: C++
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2023-04-07
- **Last Updated**: 2024-02-28

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 总结

### 技巧

#### sort

```
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
struct Stu{
	int sa,sae;
	
} stu[1010];
bool cmp(Stu a,Stu b)
{
	return a.sae<b.sae;
}
int n,s,a,e;
LL res;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	{
	cin>>s>>a>>e;
	stu[i].sa=s+a;
	stu[i].sae=s+a+e;		
	}
	sort(stu,stu+n+1,cmp);
	int sum=0;
	
//	for(int i=1;i<=n;i++)
//	{
//	cout<<stu[i].sa<<' ';
//	cout<<stu[i].sae<<'\n';
//
//	}
	
	for(int i=1;i<=n;i++){
	
		res+=sum+stu[i].sa;
//		cout<<res<<" ";
	
		sum+=stu[i].sae;
	}
	cout<<res;
	return 0;
}

```



#### 反转数组

```
reverse(a, a+n);//n为数组中的元素个数
```



#### 等价

```
i>=0等价于~i //等价于取反i
int mid = l + r >> 1;
////
///int d[]={上，右，下，左}
int dx[] = {-1, 0, 1, 0};//向上x-1，向下x+1
int dy[] = {0, 1, 0, -1};//向左y-1，向右y+1
//pi 3.1415926535897
const double PI = acos(-1);
```

#### 闰年

```
#include <iostream>
using namespace std;
int main() {
    int y;
    cin >> y;
    if ((y % 4 == 0 && y %100 != 0) || y % 400 == 0)
        cout << "yes";
    else
        cout << "no";
    return 0;
}
```

#### 时间转换

```
#include <iostream>
using namespace std;
int main() {
    int h = 0, m = 0, s = 0, t;
    cin >> t;
    h = t / 3600;//时
    t = t % 3600;
    m = t / 60;//分
    t = t % 60;
    s = t;//秒
    cout << h << ":" << m << ":" << s;
    return 0;
}
```

#### 三角形面积

```
//海伦公式
#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    double s = (a + b + c) / 2.0;
    printf("%.2f", sqrt(s * (s - a) * (s - b) * (s - c)));
    return 0;
}
//三角形在坐标轴中的面积公式
S=(1/2)*abs((x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2));



```

#### 回文数

##### 一般

```
#include <iostream>
using namespace std;
int main() {
    for (int i = 1; i <= 9; i++) {
        for (int j = 0; j <= 9; j++) {
            cout << i << j << j << i << endl;
        }
    }
    return 0;
}
```

##### 特殊

```
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    for (int i1 = 1; i1 <= 9; i1++)
        for (int i2 = 0; i2 <= 9; i2++)
            for (int i3 = 0; i3 <= 9; i3++) {
                if ((i1 + i2 + i3 + i2 + i1) == n)
                    cout << i1 << i2 << i3 << i2 << i1 << endl;
            }
    for (int i1 = 1; i1 <= 9; i1++)
        for (int i2 = 0; i2 <= 9; i2++)
            for (int i3 = 0; i3 <= 9; i3++) {
                if ((i1 + i2 + i3 + i3 + i2 + i1) == n)
                    cout << i1 << i2 << i3 << i3 << i2 << i1 << endl;
            }
    return 0;
}
```



#### 常用数据类型

```
typedef pair<int, int> PII;//二元组
typedef pair<double, double> PDD;

typedef unsigned long long ULL;

typedef long long LL;

const int N = 3e8;
const double eps = 1e-8;
const double PI = acos(-1);

```

#### 常用头文件

```
#include <bits/stdc++.h>//万能头

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cstdio>//c语言输入输出 避免兼用性问题

#include <cmath>//数学

#include <vector>//

#include <queue>//队

#include <unordered_map>

#include <unordered_set>

#include <map>

#include <set>



```



#### 环境配置

```
-std=c++11//dev环境配置

```

#### 提高cin cout速度

```
//用来关闭iostream与stdio的同步，从而提高 cin cout 的效率，但是就不能再用 scanf printf了，
//因为不关闭之前是C++为了与C兼容，以免 cout 与 printf 一块使用时造成混乱，才打开同步，这样可以提高一定的效率。
ios::sync_with_stdio(false); 
//解除输入输出流（ cin与cout ）的绑定
    cin.tie(0);
    cout.tie(0);
    
#include <iostream>
using namespace std;
int main() {
	// 关闭输入输出缓存，使效率提升
	ios::sync_with_stdio(false);
	// 解除cin和cout的默认绑定，来降低IO的负担使效率提升
	cin.tie(NULL); cout.tie(NULL);
	
	return 0;
}
 
 
    



```



### C++中未初始化的数组的默认值

#### int类型

1. 全局数组，未初始化时，默认值都是 0；
2. 局部数组，未初始化时，默认值为随机的不确定的值；
3. 局部数组，初始化一部分时，未初始化的部分默认值为 0；

#### double ，float 型数组

1. 全局数组，未初始化时，默认值都是 0.0；
2. 局部数组，未初始化时，默认值为随机的不确定的值；
3. 局部数组，初始化一部分时，未初始化的部分默认值为 0.0；

#### char 型数组

1. 全局数组，未初始化的部分，默认值为 ‘ ’ ；
2. 局部数组，初始化一部分后，未初始化部分默认值为 ‘ ’ ；
3. 局部数组，未初始化时，默认值不可预知。

#### bool 型数组

1. 全局数组，未初始化时，默认值都是 0；
2. 局部数组，未初始化时，默认值为 204；
3. 局部数组，初始化一部分时，未初始化的部分默认值为 0；



### 快速排序 

![快速排序](快速排序.png)





![快速排序2](快速排序2.png)

```
//模板
int q[N]//待排序数组
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;//边界条件 没有数或者只有一个数

    int i = l - 1, j = r + 1, x = q[l + r >> 1];//先移动指针在判断 x为初始分界点 或者x=q[l];
    
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);//或者{int t=q[i]; q[i]=q[j];q[j]=t;}
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);//递归处理左右两边
}

```

### 归并排序

![归并排序](归并排序.png)



![归并排序2](归并排序2.png)



![归并排序3](归并排序3.png)



```
//模板
int q[N],temp[N]；//temp辅助数组 存储合并结果
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;//边界条件 没有数或者只有一个数

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;//k当前已合并的数的数量
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];//合并
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];//某一数组到头 另一数组加入到temp中
    while (j <= r) tmp[k ++ ] = q[j ++ ]; //某一数组到头 另一数组加入到temp中

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];//赋值回原数组
}

```





### 前缀和

#### 一维前缀和

前缀和：指的是用一个数组sum[n]表示数组a[n]的前i项和。
求法：
for(int i = 1; i <= n ; i ++)
sum[i] = sum[i - 1] + a[i];
计算前缀和时数组下标一定要从1开始，方便计算。
用法：前缀和可以用O(1)的复杂度来求某一区间的和，比如求l ~ r区间和可以用sum[r] - sum[l - 1]来计算，常用于需要多次查找某一区间和的问题。
————————————————
版权声明：本文为CSDN博主「magnte」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/magnte/article/details/119121125

```c++
#include<bits/stdc++.h>
using namespace std;

const int N = 100010;

int a[N],sum[N],n,m;

int main()
{
    cin>>n>>m;
    for(int i = 1; i <= n; i ++ )
    {
        cin>>a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    int l,r;
    while(m -- )
    {
        cin>>l>>r;
        cout<<sum[r] - sum[l - 1]<<endl;
    }
    return 0;
}


```

#### 二维前缀和

![二维前缀和](二维前缀和.png)

```
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：

S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

 for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];



int sum(int x1, int y1, int x2, int y2)
{
    return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}


```



### 差分数组

#### 一维差分

```
a[1].a[2],...a[n]
b[i]=a[i]-a[i-1],b[1]=a[1]

a[i]=b[1]+b[2]+...+b[i]
	=a[1]+a[2]-a[1]+a[3]-a[2]+...+a[i]-a[i-1]
	=a[i]
给区间[l, r]中的每个数加上c：b[l] += c, b[r + 1] -= c





```

#### 二维差分

```
给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

```



### 高精度

#### 高精度加法

```
// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}
```

#### 高精度减法

```
// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
```

#### 高精度乘低精度

```
// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}
```

#### 高精度除以低精度

```
// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
```





### 二分

**有单调性就可以二分，没有不一定不能二分**

![二分](二分.png)



#### 整数二分算法模板

```
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：



int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}

// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：



int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}




```

#### 浮点数二分算法模板

```
bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}
```



### 位运算

#### 求n的第k位数字: 

![第k位](第k位.png)

```c++
n >> k & 1

```

#### 返回n的最后一位1：

![第k位](第k位.png)

```c++
lowbit(n) 
{
	return n & -n;
}

```

![1的个数](1的个数.png)

### 离散化

![离散化](离散化.png)

```
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n 去掉1从0开始映射
}

```

#### 区间和

```
#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;

const int N = 300010;
int a[N], al;
int b[N], s[N]; // 假定有一个无限长的数轴，数轴上每个坐标上的数都是 0

PII q[N], p[N];
int ql, pl;

int n, m;

// 手写二分
int lower_bound(int q[], int l, int r, int x) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if (q[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

int main() {
    cin >> n >> m;
    while (n--) {
        int x, c;
        cin >> x >> c;
        p[pl++] = {x, c};
        a[al++] = x;
    }

    int l, r;
    while (m--) {
        cin >> l >> r;
        q[ql++] = {l, r};
        a[al++] = l, a[al++] = r;
    }

    // ① 排序+去重
    sort(a, a + al);
    // ② 使用STL的去重函数去重，不用手写的去重，原因：只排序一次，去重一次，不像是二分需要重复使用，性能差别不大，但代码就短的多
    al = unique(a, a + al) - a;

    // 处理一下某个x上加c的事情
    for (int i = 0; i < pl; i++) {
        int x = lower_bound(a, 0, al, p[i].first) + 1; // 下标从0开始，需要加1个偏移量
        b[x] += p[i].second;
    }

    // 一维前缀和
    for (int i = 1; i < N; i++) s[i] = s[i - 1] + b[i];

    // 处理询问(前缀和应用)
    for (int i = 0; i < ql; i++) {
        // 根据原来的位置值，计算出映射后的位置值
        l = lower_bound(a, 0, al, q[i].first) + 1;
        r = lower_bound(a, 0, al, q[i].second) + 1;
        // 利用一维前缀和计算区间和
        printf("%d\n", s[r] - s[l - 1]);
    }
    return 0;
}

```



### 区间合并

```
// 将所有存在交集的区间合并
#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;
vector<PII> segs;
vector<PII> res;
void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());//排序 PII优先以左端点排序

    int st = -2e9, ed = -2e9;//设定边界
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }//在区间内
        else ed = max(ed, seg.second);//有交集

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}

```

```
#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;
vector<PII> segs;
vector<PII> res;

void merge() {
    if (!segs.size()) return; // 本题中没有实际意义，为了防止下面segs[0]越界

    // ① 按左端点排序
    sort(segs.begin(), segs.end());
    int st = segs[0].first, ed = segs[0].second;     // 第一只猴子默认为大王
    for (int i = 1; i < segs.size(); i++)            // 后续的猴子开始枚举
        if (ed < segs[i].first) {                    // ② 无交集
            res.push_back({st, ed});                 // 发现新大陆
            st = segs[i].first, ed = segs[i].second; // 重新设置起始、终止值
        } else                                       // ③ 有交集
            ed = max(ed, segs[i].second);            // PK最大值

    // ③ 残余势力入数组
    res.push_back({st, ed});
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    merge();
    printf("%d\n", res.size());
    return 0;
}

```



### 并查集

![并查集](并查集.png)

![并查集2](并查集2.png)

![并查集优化](并查集优化.png)



#### 朴素并查集

```c++
 int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点
    int find(int x) 
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n 将父节点设为自己
    for (int i = 1; i <= n; i ++ ) p[i] = i; 

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);

```

![并查集合并](并查集合并.png)

#### 维护size的并查集

```c++
    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
          return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);

```

#### 维护到祖宗节点距离的并查集

```c++
 int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

```



### 双指针（优化O(n)）

![双指针](双指针.png)

![输出字符串](输出字符串.png)

![最长序列](最长序列.png)

```c++
for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
```

### 区间合并

```c++
// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}


```

### 单链表

![单链表](单链表.png)

![单链表2](单链表2.png)

```
// head存储链表头头节点下表，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert_head(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;//存储值//head指向的位置存入当前next指针// head指向当前位置 //idx++
}
// 在下标k位置处插入一个数a
void insert_k(int k,int a)
{
    e[idx] = a, ne[idx] = ne[k], ne[k]= idx ++ ;//存储值//k指向的位置存入当前next指针// k指向当前位置 //idx++
}
// 将下标k位置后面的点删除
void remove(int k)
{
   ne[k] = ne[ne[k]];
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}
```

### 双链表 

![双链表](双链表.png)

```
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}
// 在节点a的左边插入一个数x

void insert(int a, int x)
{
	a=l[a];//a左边数的右边插入
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}
// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}


```

### 栈

```
// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空，如果 tt > 0，则表示不为空
if (tt > 0)
{

}
```

#### 单调栈（**动态维护一个栈，把后续问题的答案都维持在这个栈中，把肯定不再有用的数字从栈中去掉。）**

![单调栈](单调栈.png)

```
常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}
```

**给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。**

```
#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
int stk[N], tt;
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        while (tt && x <= stk[tt]) tt--;
        if (tt == 0)
            cout << "-1 ";
        else
            cout << stk[tt] << " ";
        stk[++tt] = x;
    }
    return 0;
}

```



### 队列

#### 普通队列：

```
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)
{

}
```

#### 循环队列

```
// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空，如果hh != tt，则表示不为空
if (hh != tt)
{

}
```

#### 单调队列

```
常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}

```

**滑动窗口最值**

```
# include <iostream>
using namespace std;
const int N = 1000010;
int a[N], q[N], hh, tt = -1;

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++ i)
    {
        scanf("%d", &a[i]);
        if (i - k + 1 > q[hh]) ++ hh;                  // 若队首出窗口，hh加1
        while (hh <= tt && a[i] <= a[q[tt]]) -- tt;    // 若队尾不单调，tt减1
        q[++ tt] = i;                                  // 下标加到队尾
        if (i + 1 >= k) printf("%d ", a[q[hh]]);       // 输出结果
    }//最小值
    cout << endl;
    hh = 0; tt = -1;                                   // 重置！
    for (int i = 0; i < n; ++ i)
    {
        if (i - k + 1 > q[hh]) ++ hh;
        while (hh <= tt && a[i] >= a[q[tt]]) -- tt;
        q[++ tt] = i;
        if (i + 1 >= k) printf("%d ", a[q[hh]]);
    }//最大值
    return 0;
}


```



### KMP

```c++
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

```

### Trie树



![Trie](Trie.png)



![Trie存储](Trie存储.png)

```
//高效存储查找字符串集合 适用于限制字母数字种类数量不会特别多
int son[N][26], cnt[N], idx;//26 为26个英文字母
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';//映射为0~25
        if (!son[p][u]) son[p][u] = ++ idx;//如果不存在创建
        p = son[p][u];//
    }
    cnt[p] ++ ;//该字符串数量加1
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}


```

![image-20230401134927491](image-20230401134927491.png)

```
#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
int tr[N][26], idx, cnt[N];

void insert(string str) {
    int p = 0;
    for (int i = 0; i < str.size(); i++) {
        int u = str[i] - 'a';
        if (!tr[p][u]) tr[p][u] = ++idx;
        p = tr[p][u];
    }
    cnt[p]++;
}

int query(string str) {
    int p = 0;
    for (int i = 0; i < str.size(); i++) {
        int u = str[i] - 'a';
        if (!tr[p][u]) return 0;
        p = tr[p][u];
    }
    return cnt[p];
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        char op;
        string str;
        cin >> op >> str;
        if (op == 'I')
            insert(str);
        else
            printf("%d\n", query(str));
    }
    return 0;
}

```



### 字典树

```c++
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}n


```

### 堆

![堆的操作](堆的操作.png)

![堆的基本性质](堆的基本性质.png)

![堆的存储](堆的存储.png)

```
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)//数变大下移调整
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u//数变小上移调整
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

```

![堆操作实现](堆操作实现.png)



### 哈希

#### 一般哈希 

##### (1) 拉链法

```
    int h[N], e[N], ne[N], idx;

    // 向哈希表中插入一个数
    void insert(int x)
    {
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }

    // 在哈希表中查询某个数是否存在
    bool find(int x)
    {
        int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i])
            if (e[i] == x)
                return true;

        return false;
    }

```

##### (2) 开放寻址法

```
  int h[N];

    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        {
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }
```



#### 字符串哈希

```
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}


```





### STL

![vector](vector.png)

![vector2](vector2.png)



![vector比较运算](vector比较运算.png)

![pair比较运算](pair比较运算.png)



![pair构造](pair构造.png)

![pair构造2](pair构造2.png)



```
vector, 变长数组，倍增的思想
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序

pair<int, int>
    first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string，字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标，(子串长度))  返回子串
    c_str()  返回字符串所在字符数组的起始地址

queue, 队列
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素

priority_queue, 优先队列，默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素

deque, 双端队列
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继，时间复杂度 O(logn)

    set/multiset
        insert()  插入一个数
        find()  查找一个数
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  返回有多少个1

    any()  判断是否至少有一个1
    none()  判断是否全为0

    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反


```



### 邻接表

```
int h[N], e[M], w[M], ne[M], idx; //邻接表 N节点个数，M边个数
int w[N];  // 用来存储每条边的权重
/*其中 
h[a] 指向a节点起点的邻接表列表的最后一个元素。
e[idx] 为当前idx编号的边指向的终点节点
w[idx] 为当前idx编号的边权重
ne 存储邻接表链表，当前值对应邻接表中下一个的地址，类似于值是指针。
 */
//初始化
idx = 0;//编号
memset(h, -1, sizeof h);
 
void add(int a, int b, int c) {	//构建邻接表
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a]; 
    h[a] = idx++;	//h[a] 一直指向a邻接表头插法起点，其实是最后一个，指针保留的方式也是向前
}


/*
1. idx一直向前，如果a是第一次出现，则h[a]的值对应ne中位置即是起点。
2. 插入的方式是类似头插法，每次邻接表中的新元素出现，则插入邻接链表的第一个。也可以这样理解，是每次插到最后，让h[a]指向最后一个元素，遍历的时候倒着向前遍历。
3. 如果指向下一个为空时，指针值为-1.
*/


for(int i = h[vel]; i != -1; i = ne[i]) { 
   //遍历
}
 
i = ne[i]	//模拟链表指针的next操作
h[vel]		//指向vel链表的最后一个，遍历是从后往前的


 
```



```
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

```



### BFS

```
时间复杂度 O(n+m)

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

```



### DFS

```
int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;
const int N = 10;
int g[N][N];//矩阵
unordered_set<int> S;
int n,m,k;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//方向

void dfs(int x,int y,int u,int num)
{
    if(u==k) S.insert(num);
        else {
            for (int i = 0; i < 4; i ++ )
            {
                int a=x+dx[i];
                int b=y+dy[i];
            if(a>=0&&a<n&&b<m&&b>=0)
            dfs(a,b,u+1,num*10+g[a][b]);
            
            }
            
            
        }
}
int main()
{
    cin>>n>>m>>k;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin>>g[i][j];
            
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            dfs(i,j,0,g[i][j]);
    
    cout <<S.size();
    return 0;
}





```

![DFS BFS对比](DFS BFS对比.png)

### 图

![图的存储](图的存储.png)

#### 图的存储

##### 有向图

```
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
const int N=1e5+10;
int h[N], e[N], ne[N], idx;//e[]节点编号

// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);//初始化-1
```

##### 无向图

```c++
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
const int N=1e5+10, M=N*2;
int h[N], e[M], ne[M], idx;

// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);//初始化-1




```



#### 图的遍历

##### dfs

```c++
bool st[N];//存储已被搜过的的点的编号
int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];//j存储对映图里的编号
        if (!st[j]) dfs(j);//没搜过继续搜
    }
}
```

##### bfs

```
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)
{

}

```



```c++
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}
```





### 拓扑排序

![拓扑排序](拓扑排序.png)

```
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)
{

}

//////模板

bool topsort()
{
    int hh = 0, tt = -1;

    // d[i] 存储点i的入度
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;

    while (hh <= tt)
    {
        int t = q[hh ++ ];

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;
}










#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N];//入度
int q[N];//队列

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
////
bool topsort()
{
    int hh = 0, tt = -1;

    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;//入度为零的点入队

    while (hh <= tt)//队列不空
    {
        int t = q[hh ++ ];//取队头元素

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

    return tt == n - 1;
}

////
int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);

        d[b] ++ ;//更新入度
    }

    if (!topsort()) puts("-1");
    else
    {
        for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);//拓扑序
        puts("");
    }

    return 0;
}


```



### 最短路

![最短路](最短路.png)

#### 朴素dijkstra算法（适用于：正权边稠密图）贪心

![朴素Dijkstra过程](朴素Dijkstra过程.png)

```c++
int g[N][N];  // 存储每条边稠密图邻接矩阵存储
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);//初始化
    dist[1] = 0;//自己到自己的最短距离为0

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j])) //所有st为false的点中找到一个dist最小的点
                t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;//加入到已确定最短距离
    }

    if (dist[n] == 0x3f3f3f3f) return -1;//没有最短距离
    return dist[n];
}



```

##### 例题

![image-20230403153115749](image-20230403153115749-16805070814071.png)

![image-20230403153207493](image-20230403153207493.png)



假设图中一共有n个点，下标为1~n。下面所说的某个点的距离，都是指该点到起点（1号点）的距离。

算法步骤如下，用一个集合s来存放最短距离已经确定的点。

初始化距离，d[1] = 0， d[i] = +∞。即，将起点的距离初始化为0，而其余点的距离当前未确定，用正无穷表示。

循环

每次从距离已知的点中，选取一个不在s集合中，且距离最短的点（这一步可以用小根堆来优化），遍历该点的所有出边，更新这些出边所连接的点的距离。并把该次选取的点加入到集合s中，因为该点的最短距离此时已经确定。

当所有点都都被加入到s中，表示全部点的最短距离都已经确定完毕

注意某个点的距离已知，并不代表此时这个点的距离就是最终的最短距离。在后续的循环中，可能用一条更短距离的路径，去更

##### 题解

```
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))//所有st为false的点中找到一个dist最小的点
                t = j;
		//if(t==n) break;//优化 已经找到最短距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(g, 0x3f, sizeof g);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);

        g[a][b] = min(g[a][b], c);
    }

    printf("%d\n", dijkstra());

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/48488/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 510;
const int INF = 0x3f3f3f3f; // 正无穷
int g[N][N]; // 稠密图采用邻接矩阵存储
int d[N]; // 距离
int n, m;
bool visited[N];

int dijkstra() {
	d[1] = 0;
	// 每次
	for(int i = 1; i <= n; i++) {
		//找到一个距起点距离最小的点
		int t = 0; // d[0]未被使用, 其值一直是 INF
		for(int j = 1; j <= n; j++) {
			if(!visited[j] && d[j] < d[t]) {
				t = j;
			}
		}
		if(t == 0) break; // 未找到一个点, 提前break
		// 找到该点
		visited[t] = true; // 放入集合s
		// 更新其他所有点的距离
		for(int i = 1; i <= n; i++) {
			d[i] = min(d[i], d[t] + g[t][i]);
		}
	}
	if(d[n] == INF) return -1;
	else return d[n];
}

int main() {
	// 初始化
	memset(d, 0x3f, sizeof d);
	memset(g, 0x3f, sizeof g);
	scanf("%d%d", &n, &m);
	while(m--) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		g[x][y] = min(g[x][y], z); // 重复边只需要保留一个权重最小的即可
	}
	printf("%d", dijkstra());
	return 0;
}


```

#### 堆优化版dijkstra （适用于：正权边稀疏图 n<1e5 m<1e5 ---n为点数，m为边数）贪心

```c++
typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边 w[]边权重
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号 放入一号点

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}


```

##### 例题

![image-20230403170654494](image-20230403170654494.png)

##### 题解

```
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>//优先队列实现堆 用堆来寻找最小值

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

    while (heap.size())
    {
        auto t = heap.top();//当前最小
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;//已经处理过
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    printf("%d\n", dijkstra());

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/48493/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
```



#### Bellman-Ford（适用于：负权边对最短路边数有限制）离散数学

![Bellman-Ford](Bellman-Ford.png)

![负权回路不存在最短路](负权回路不存在最短路.png)

```
//可用结构体存储图
int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

```

##### 例题

![image-20230404091808123](image-20230404091808123.png)

![image-20230404095216917](image-20230404095216917.png)

##### 题解

```
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, M = 10010;

struct Edge
{
    int a, b, c;
}edges[M];

int n, m, k;
int dist[N];
int last[N];

void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;
    for (int i = 0; i < k; i ++ )
    {
        memcpy(last, dist, sizeof dist);
        for (int j = 0; j < m; j ++ )
        {
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], last[e.a] + e.c);
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);

    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = {a, b, c};//读入边
    }

    bellman_ford();

    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");//可能会更新
    else printf("%d\n", dist[n]);

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/48523/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#include<iostream>
#include<cstring>
using namespace std;

const int N = 510, M = 10010;
const int INF = 0x3f3f3f3f;
struct Edge
{
	int a, b, w;
} edge[M]; // 直接用结构体来存储全部边

int n, m, k, d[N], tmp[N];

void bellman_ford() {
	memset(d, 0x3f, sizeof d);
	d[1] = 0; // 初始化
	for(int i = 0; i < k; i++) {
		memcpy(tmp, d, sizeof d); // 需要备份
		for(int j = 0; j < m; j++) {
			Edge e = edge[j];
			int a = e.a, b = e.b, w = e.w;
			if(tmp[a] == INF) continue;
			if(d[b] > tmp[a] + w) { 
                // 用备份的tmp来进行计算, 以防出现串联更新的情况
                // 串联更新虽然不影响最终的最短距离, 但会影响[经过不超过k条边的最短距离]这个语义
                // 比如在外层循环进行了2次时, 此时应当找到了从起点到其他点,经过不超过2条边的最短距离
                // 而如果串联更新的话, 可能在这第2次循环时, 已经更新了多次, 得到的最短距离是经过了3条边的最短距离
                
                // 另外, 上面的if中应该用 d[b] > tmp[a] + w
                // 而不应当用 tmp[b] > tmp[a] + w
                // 当a和b之间存在重边时, 若使用后者作为条件, 则无法取到a,b之间权重最小的那条边
				// 更新
				d[b] = tmp[a] + w;
			}
		}
	}
	if(d[n] == INF) printf("impossible");
	else printf("%d", d[n]);
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 0; i < m; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		edge[i] = {x, y, z};
	}
	bellman_ford();
	return 0;
}


```



#### spfa 算法（适用于：负权边（优先选择该算法）也可以用于正权边(可能被卡O(mn)) 队列优化的Bellman-Ford算法）离散数学

![Bellman-Ford优化宽搜](Bellman-Ford优化宽搜.png) 只有 dist[a]变小才会更新

![spfa卡常数网格图](spfa卡常数网格图.png)

```
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中//防止存储重复的点

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}



```

##### 例题

![image-20230404095244564](image-20230404095244564.png)

![image-20230404095259494](image-20230404095259494.png)

##### 题解

```
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size())
    {
        int t = q.front();
        q.pop();//出队

        st[t] = false;//去除该点

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    int t = spfa();

    if (t == 0x3f3f3f3f) puts("impossible");
    else printf("%d\n", t);

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/48498/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1e5 + 10;

const int INF = 0x3f3f3f3f;

int h[N], e[N], w[N], ne[N], idx;

int n, m;

int d[N];

int q[N], hh, tt = -1;

bool st[N];

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

void spfa() {
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    q[++tt] = 1;
    st[1] = true;
    while(tt >= hh) {
        int u = q[hh++];
        st[u] = false;
        for(int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if(d[j] > d[u] + w[i]) {
                d[j] = d[u] + w[i];
                if(!st[j]) {
                    // 为了防止已在队列中的点, 被重复添加进队列
                    // 虽然不影响最终结果, 但会拖慢一点性能
                    st[j] = true;
                    q[++tt] = j;
                }
            }
        }
    }
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    while(m--) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    spfa();
    if(d[n] != INF) printf("%d", d[n]);
    else printf("impossible");
    return 0;
}

```

##### spfa判断负环

![spfa判断负环](spfa判断负环.png)



![spfa判断负环2](spfa判断负环2.png)

```
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N], cnt[N];        // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N];     // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。

    queue<int> q;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        st[i] = true;//所有点都放入队列
    }

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}


```

![image-20230404100930582](image-20230404100930582.png)

![image-20230404100943867](image-20230404100943867.png)

```
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 2010, M = 10010;

int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N], cnt[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa()
{
    queue<int> q;

    for (int i = 1; i <= n; i ++ )
    {
        st[i] = true;
        q.push(i);
    }

    while (q.size())
    {
        int t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;

                if (cnt[j] >= n) return true;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    if (spfa()) puts("Yes");
    else puts("No");

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/48499/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
#include<iostream>
#include<cstring>
using namespace std;

const int N = 1e4 + 10, M = 1e8 + 10;

const int INF = 0x3f3f3f3f;

int h[N], e[N], w[N], ne[N], idx;

int n, m;

int d[N], ctn[N];

bool st[N];

int q[M], hh, tt = -1;

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool spfa() {
    for(int i = 1; i <= n; i++) {
        q[++tt] = i;
        st[i] = true;
    }

    while(tt >= hh) {
        int u = q[hh++];
        st[u] = false;
        for(int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if(d[j] > d[u] + w[i]) {
                d[j] = d[u] + w[i];
                ctn[j] = ctn[u] + 1;
                if(ctn[j] >= n) return true;
                if(!st[j]) {
                    q[++tt] = j;
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    while(m--) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    if(spfa()) printf("Yes");
    else printf("No");
    return 0;
}

```



#### floyd算法（多源汇最短路）动态规划

![floyd算法](floyd算法.png)

![floyd算法动态规划](floyd算法动态规划.png)

![floyd算法动态规划2](floyd算法动态规划2.png)

负权回路

```
初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;//邻接矩阵

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}


```

##### 例题

![image-20230404110923323](image-20230404110923323.png)

![image-20230404110953646](image-20230404110953646.png)

##### 题解

```
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 210, INF = 1e9;

int n, m, Q;
int d[N][N];

void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main()
{
    scanf("%d%d%d", &n, &m, &Q);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        d[a][b] = min(d[a][b], c);
    }

    floyd();

    while (Q -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);

        int t = d[a][b];
        if (t > INF / 2) puts("impossible");
        else printf("%d\n", t);
    }

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/48531/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 210, INF = 0x3f3f3f3f;
int g[N][N]; // 邻接矩阵存储
int n, m, k;

void floyd() {
	for(int p = 1; p <= n; p++) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(g[i][p] != INF && g[p][j] != INF) g[i][j] = min(g[i][j], g[i][p] + g[p][j]);
			}
		}
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			if(i == j) g[i][j] = 0;
			else g[i][j] = INF;
		}
	}
	while(m--) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		g[x][y] = min(g[x][y], z); // 处理重边
	}
	floyd();
	while(k--) {
		int x, y;
		scanf("%d%d", &x, &y);
		if(g[x][y] == INF) printf("impossible\n");
		else printf("%d\n", g[x][y]);
	}
	return 0;
}

```





### 最小生成树（一般为无向图）

![最小生成树](最小生成树.png)



#### 朴素版prim算法

![Prime](Prime.png)

```
int n;      // n表示点数
int g[N][N];        // 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中


// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}


```

##### 例题

![image-20230404162649831](image-20230404162649831.png)

![image-20230404162701811](image-20230404162701811.png)

##### 题解

```
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];


int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;// 最小生成树中所有边的长度之和
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;//找到当前距离最小的点

        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);//这点到集合的距离与dijsitra的区别//min放到最后防止自环
    }

    return res;
}


int main()
{
    scanf("%d%d", &n, &m);

    memset(g, 0x3f, sizeof g);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int t = prim();

    if (t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/48767/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N], d[N];
bool visited[N];

void prim() {
	memset(d, 0x3f, sizeof d); // 初始化距离为正无穷
	int sum = 0;
	for(int i = 1; i <= n; i++) {
		// 循环n次
		// 选出距离集合s最小的点
		int t = 0;
		for(int j = 1; j <= n; j++) {
			if(!visited[j] && d[j] <= d[t]) t = j; // 这里用<=, 可以避免对第一次选点做特判
		}
		if(i == 1) d[t] = 0;// 第一次加入集合的点, 其到集合的距离为0
		if(d[t] == INF) {
		    // 选中的点距离是正无穷, 无效
		    printf("impossible\n");
		    return;
		}
		// 把这个点放到集合s里
		visited[t] = true; 
		sum += d[t]; // 这次放进来的
		// 更新其他点到集合s的距离, 
		for(int j = 1; j <= n; j++) {
			if(!visited[j] && g[t][j] != INF && g[t][j] < d[j]) {
			    d[j] = g[t][j];
			}
		}
	}
	printf("%d\n", sum);
}

int main() {
	memset(g, 0x3f, sizeof g);
	scanf("%d%d", &n, &m);
	while(m--) {
		int x, y, w;
		scanf("%d%d%d", &x, &y, &w);
		g[x][y] = min(g[x][y], w);
		g[y][x] = g[x][y];
	}
	prim();
	return 0;
}

```







#### Kruskal算法 

![Kruskal算法 ](Kruskal算法 .png)

```
int n, m;       // n是点数，m是边数
int p[N];       // 并查集的父节点数组

struct Edge     // 存储边
{
    int a, b, w;

    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[M];

int find(int x)     // 并查集核心操作
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b)     // 如果两个连通块不连通，则将这两个连通块合并
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }

    if (cnt < n - 1) return INF;
    return res;
}


```

##### 例题

![image-20230404164922478](image-20230404164922478.png)

![image-20230404164933443](image-20230404164933443.png)

##### 题解

```
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010, INF = 0x3f3f3f3f;

int n, m;
int p[N];

struct Edge
{
    int a, b, w;

    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[M];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b)//是否连通
        {
            p[a] = b;//边合并
            res += w;//最小生成树边权值之和
            cnt ++ ;//边数
        }
    }

    if (cnt < n - 1) return INF;
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 0; i < m; i ++ )
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
    }

    int t = kruskal();

    if (t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;
}

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/48773/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;

struct Edge {
	int a, b, w;
	bool operator < (const Edge& W) {
		return w < W.w;
	}
} edges[M];

int n, m;
int p[N];

int find(int x) {
	if(x != p[x]) p[x] = find(p[x]);
	return p[x];
}

void kruskal() {
	// 先对所有边从小到大排序
	sort(edges, edges + m);
	int totalW = 0, edgeCtn = 0;
	// 枚举全部边
	for(int i = 0; i < m; i++) {
		int a = edges[i].a, b = edges[i].b, w = edges[i].w;
		a = find(a);
		b = find(b);
		if(a != b) {
			// 若a和b不连通, 则加入这条边
			p[a] = b; // 将a和b连通
			totalW += w;
			edgeCtn++;
		}
	}
	if(edgeCtn == n - 1) printf("%d\n", totalW);
	else printf("impossible\n");
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 0; i < m; i++) {
		int a, b, w;
		scanf("%d%d%d", &a, &b, &w);
		edges[i] = {a, b, w};
	}

	for(int i = 1; i <= n; i++) p[i] = i;

	kruskal();

	return 0;
}

```



### 二分图 

![二分图](二分图.png)



#### 染色法判别二分图

```
int n;      // n表示点数
int h[N], e[M], ne[M], idx;     // 邻接表存储图
int color[N];       // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色

// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (color[j] == -1)
        {
            if (!dfs(j, !c)) return false;
        }
        else if (color[j] == c) return false;
    }

    return true;
}

bool check()
{
    memset(color, -1, sizeof color);
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (color[i] == -1)
            if (!dfs(i, 0))
            {
                flag = false;
                break;
            }
    return flag;
}


```

#### 匈牙利算法

```
int n1, n2;     // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx;     // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N];       // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N];     // 表示第二个集合中的每个点是否已经被遍历过

bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }

    return false;
}

// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
    memset(st, false, sizeof st);
    if (find(i)) res ++ ;
}


```

### 数学

#### 秦九韶算法

```
//转十进制
int base(string s, int b)//b进制
{
    int res = 0;
    for (auto x: s)//auto 自动识别类型 此处为char
        res = res * b + x - '0';
    return res; 
}
```



#### 最大公约数

```
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
```

#### 质数

##### 试除法判定质数

```
bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}
```

##### 试除法分解质因数

```
void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}
```

##### 朴素筛法求素数

```
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}
```

##### 线性筛法求素数 

```
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}


处。
```



#### 快速幂

```
//v求 m^k mod p，时间复杂度 O(logk)。

int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}
```

#### 递推法求组合数

```
// c[a][b] 表示从a个苹果中选b个的方案数
for (int i = 0; i < N; i ++ )
    for (int j = 0; j <= i; j ++ )
        if (!j) c[i][j] = 1;
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
```



### DP

![dp时间复杂度](dp时间复杂度.png)



#### 背包DP

##### 01背包

```

```

##### 完全背包

##### 分组背包

##### 多重背包



#### 线性DP

![下标定义](下标定义.png)

**出现 i-1 时 下标最好从1开始**

![线性dp](线性dp.png)

##### 例题1数字三角形

![image-20230405153023743](image-20230405153023743.png)

##### ![image-20230405153045422](image-20230405153045422.png)题解

```
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;

int n;
int a[N][N];//三角形
int f[N][N];//状态表示

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            scanf("%d", &a[i][j]);

    for (int i = 0; i <= n; i ++ )
        for (int j = 0; j <= i + 1; j ++ )
            f[i][j] = -INF;//一行要多初始化一个

    f[1][1] = a[1][1];
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);

    int res = -INF;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);

    printf("%d\n", res);
    return 0;
}



```

##### 例题2最长上升子序列

![image-20230405162640511](image-20230405162640511.png)



![最长上升子序列](最长上升子序列.png)

##### 题解

```
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int a[N], f[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i ++ )
    {
        f[i] = 1; // 只有a[i]一个数
        for (int j = 1; j < i; j ++ )
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);

    printf("%d\n", res);

    return 0;
}


```

##### 例题3最长公共子序列

![image-20230405190754597](image-20230405190754597.png)

##### ![最长公共子序列](最长公共子序列.png)

##### 题解

```
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s%s", a + 1, b + 1);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }

    printf("%d\n", f[n][m]);

    return 0;
}
///////////////////////////////////////////////////
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
char a[N],b[N];
int f[N][N];
int n,m;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
		f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        	if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
		}
			
		cout<<f[n][m];
		
	return 0;
}




```



#### 区间DP

![区间dp](区间dp.png)

![区间dp2](区间dp2.png)

##### 例题1合并石子

![image-20230405223218231](image-20230405223218231.png)

![image-20230405223233774](image-20230405223233774.png)

##### 题解

```
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310;

int n;
int s[N];
int f[N][N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);

    for (int i = 1; i <= n; i ++ ) s[i] += s[i - 1];

    for (int len = 2; len <= n; len ++ )//枚举长度 只有一堆时不费体力
        for (int i = 1; i + len - 1 <= n; i ++ )//枚举起点
        {
            int l = i, r = i + len - 1;
            f[l][r] = 1e8;
            for (int k = l; k < r; k ++ )
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }

    printf("%d\n", f[1][n]);
    return 0;
}

////////////////////
```



#### 计数类DP

```

```



#### 数位统计DP

![数位统计dp](数位统计dp.png)

![数位统计dp2](数位统计dp2.png)

##### 例题1计数问题

![image-20230406145230141](image-20230406145230141.png)





##### 题解

```

```



#### 状态压缩DP

![状态压缩dp蒙德里安的梦想](状态压缩dp蒙德里安的梦想.png)

##### 例题1蒙德里安的梦想

![image-20230406152127693](image-20230406152127693.png)

![image-20230406152145192](image-20230406152145192.png)



##### 题解

```
/*
下文对  if ((j & k ) == 0 && st[ j | k] )  有清晰的解释！！！
*/


#include <bits/stdc++.h>
using namespace std;


const int N = 12, M = 1<< N;  

long long f[N][M] ;// 第一维表示列， 第二维表示所有可能的状态

bool st[M];  //存储每种状态是否有奇数个连续的0，如果奇数个0是无效状态，如果是偶数个零置为true。

//vector<int > state[M];  //二维数组记录合法的状态
vector<vector<int>> state(M);  //两种写法等价:二维数组

int m, n;

int main() {

    while (cin >> n >> m, n || m) { //读入n和m，并且不是两个0即合法输入就继续读入

        //第一部分：预处理1
        //对于每种状态，先预处理每列不能有奇数个连续的0

        for(int i = 0; i < (1 << n); i ++) {

            int cnt = 0 ;//记录连续的0的个数

            bool isValid = true; // 某种状态没有奇数个连续的0则标记为true

            for(int j = 0; j < n; j ++) { //遍历这一列，从上到下

                 if ( (i >> j) & 1) {  
                     //i >> j位运算，表示i（i在此处是一种状态）的二进制数的第j位； 
                     // &1为判断该位是否为1，如果为1进入if
                    if (cnt & 1) { 
                    //这一位为1，看前面连续的0的个数，如果是奇数（cnt &1为真）则该状态不合法
                        isValid =false; break;
                    } 

                    cnt = 0; // 既然该位是1，并且前面不是奇数个0（经过上面的if判断），计数器清零。
                    //其实清不清零没有影响
                 }
                 else cnt ++; //否则的话该位还是0，则统计连续0的计数器++。
            }
            if (cnt & 1)  isValid = false; //最下面的那一段判断一下连续的0的个数

            st[i]  = isValid; //状态i是否有奇数个连续的0的情况,输入到数组st中
        }

        //第二部分：预处理2
        // 经过上面每种状态 连续0的判断，已经筛掉一些状态。
        //下面来看进一步的判断：看第i-2列伸出来的和第i-1列伸出去的是否冲突

        for (int j = 0; j < (1 << n); j ++) { //对于第i列的所有状态
            state[j].clear(); //清空上次操作遗留的状态，防止影响本次状态。

            for (int k = 0; k < (1 << n); k ++) { //对于第i-1列所有状态
                if ((j & k ) == 0 && st[ j | k]) 
                // 第i-2列伸出来的 和第i-1列伸出来的不冲突(不在同一行) 
                //解释一下st[j | k] 
                //已经知道st[]数组表示的是这一列没有连续奇数个0的情况，
                //我们要考虑的是第i-1列（第i-1列是这里的主体）中从第i-2列横插过来的，
                //还要考虑自己这一列（i-1列）横插到第i列的
                //比如 第i-2列插过来的是k=10101，第i-1列插出去到第i列的是 j =01000，
                //那么合在第i-1列，到底有多少个1呢？
                //自然想到的就是这两个操作共同的结果：两个状态或。 j | k = 01000 | 10101 = 11101
                //这个 j|k 就是当前 第i-1列的到底有几个1，即哪几行是横着放格子的

                    state[j].push_back(k);  
                    //二维数组state[j]表示第j行， 
                    //j表示 第i列“真正”可行的状态，
                    //如果第i-1列的状态k和j不冲突则压入state数组中的第j行。
                    //“真正”可行是指：既没有前后两列伸进伸出的冲突；又没有连续奇数个0。
            }

        }

        //第三部分：dp开始

        memset(f, 0, sizeof f);  
        //全部初始化为0，因为是连续读入，这里是一个清空操作。
        //类似上面的state[j].clear()

        f[0][0] = 1 ;// 这里需要回忆状态表示的定义
        //按定义这里是：前第-1列都摆好，且从-1列到第0列伸出来的状态为0的方案数。
        //首先，这里没有-1列，最少也是0列。
        //其次，没有伸出来，即没有横着摆的。即这里第0列只有竖着摆这1种状态。

        for (int i = 1; i <= m; i ++) { //遍历每一列:第i列合法范围是(0~m-1列)
            for (int j = 0; j < (1<<n); j ++) {  //遍历当前列（第i列）所有状态j
                for (auto k : state[j])    // 遍历第i-1列的状态k，如果“真正”可行，就转移
                    f[i][j] += f[i-1][k];    // 当前列的方案数就等于之前的第i-1列所有状态k的累加。
            }
        }

        //最后答案是什么呢？
        //f[m][0]表示 前m-1列都处理完，并且第m-1列没有伸出来的所有方案数。
        //即整个棋盘处理完的方案数

        cout << f[m][0] << endl;

    }
}   


```



#### 树形DP

```

```



#### 记忆化搜索



##### 例题1 滑雪

![image-20230406155405278](image-20230406155405278.png)

###### 样例输入 #1

```
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
```

###### 样例输出 #1

```
25
```

###### 提示

对于 100% 的数据，1≤*R*,*C*≤100。

##### 题解

```
#include <bits/stdc++.h>

using namespace std;
const int N = 310;
int dx[] = {-1, 0, 1, 0};//向上x-1，向下x+1
int dy[] = {0, 1, 0, -1};//向左y-1，向右y+1
int g[N][N];    //邻接矩阵,地图
int f[N][N];    //记录从i到j的最大距离
int n, m;       //行与列
int res;        //结果

//记忆化搜索
int dfs(int x, int y) {
    //如果这个状态算过了话，直接返回记忆化搜索
    if (f[x][y] != -1) return f[x][y];
    //求最长的轨迹，最起码是1，不能再小了
    f[x][y] = 1;
    //四个方向去检查
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[x][y] > g[nx][ny])
            f[x][y] = max(f[x][y], dfs(nx, ny) + 1);
    }
    return f[x][y];
}

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    cin >> n >> m; //n行 m列
    //读入每一个点的高度
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];
    //初始化-1，表示没有被算过
    memset(f, -1, sizeof f);
    //模拟从每一个点出发
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            res = max(res, dfs(i, j));
    //输出结果
    printf("%d\n", res);
    return 0;
}

```



### 贪心