acwing算法笔记-图论

树和图

  1. 树是一种特殊的图，无环连通图。
  2. 图的话分为两种，有向图（a->b)和无向图(a<->b)，无向图是一种特殊的有向图,所以只需要考虑有向图就行。
  3. 有向图的存储分为两种，第一种是邻接矩阵（g[a][b]二维数组),空间复杂度比较高$O(n^2)$，有权重的话g[a][b]指的是权重,无权重的话就是bool值，表示有边或者无边。比较适合存储稠密图
  4. 另一种是邻接表（其实就是每个节点开个单链表）,存这个点可以走到哪个点，次序是无关的，插入节点是用头插法

树与图的深度优先遍历

首先我们要明确一个概念，那就是树是一种特殊的图，也就是无环连通图。
所以如果一个树有n个节点，那么对于任意两个节点之间有两条边，也就是2n - 2条边

然后对于树我们一般用邻接表来存，邻接表其实就是多个单链表。

关于节点，链表，邻接表，以及如何用邻接表表示树，这其中涉及到的概念很容易混淆，我们在这里进行详细的解读

完全解读

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//为了方便快速转化，这里列出一些常见的操作

// 1. 地址，指针，下标 （这三个词基本可以等价）
// 2. 地址（唯一）可以指代节点，所以指针or下标可以直接指代节点
// 3. 常见操作一一对应

//动态
ListNode* i： 指针i，指向一个节点，简称 i的节点（不固定，因为指针会移动）
i->val: i的节点的val
i->next: i的节点的next指针
i = p: 指针i移动到指针p的位置
i->next = p: i的节点指向p的节点

//静态
int i: 节点下标i，指向一个节点，简称 i的节点（不固定，因为下标会变）
e[i]: i的节点的val
ne[i]: i的节点的next下标
i = p: 下标i变成下标p
ne[i] = p: i的节点指向p的节点

Reference
[1]. 当前节点和邻接点的图示
[2]. 邻接表存储细节的详解


846. 树的重心

基本思路

首先我们要知道怎么找到树的重心，就是搜索每一个点，求删除该节点后的连通块中点数的最大值（简称连通块最大值），对应连通块最大值最小的那个节点就是树的重心

搜索树里的每一个点，显然用DFS或者是BFS

然后我们需要求每个节点的连通块最大值，对于每个节点的连通块最大值，我们要求每个节点的所有邻接点的连通块的值。
邻接点的连通块分为两个部分，一个是上面（一个邻接点，一个连通块），一个是下面（若干邻接点，多个连通块）

所以我们找到了突破口，下面部分的邻接点的连通块值，实际就是邻接点为根节点的树的大小（很明显求很多个节点为根节点的树的xxx用DFS递归）

然后我们DFS函数定义就是节点u的连通块最大值，在函数里面，我们先求u下面的连通块最大值，也就是遍历u所有下方邻接点得到连通块的值（实质就是以邻接点为根节点的子树大小）
然后再求u上面的连通块的值（n - 1（u节点） - u节点所有子树大小(u节点的下方邻接点的连通块值)）

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10; //数据范围是10的5次方
const int M = 2 * N; //以有向图的格式存储无向图，所以每个节点至多对应2n-2条边

int h[N]; //邻接表存储树，有n个节点，所以需要n个队列头节点
int e[M]; //存储元素
int ne[M]; //存储列表的next值
int idx; //单链表指针
int n; //题目所给的输入，n个节点
int ans = N; //表示重心的所有的子树中，最大的子树的结点数目

bool st[N]; //记录节点是否被访问过，访问过则标记为true

//a所对应的单链表中插入b  a作为根 
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

//返回以u为根的子树中节点的个数，包括u节点
int dfs(int u) {
    int res = 0; //存储 删掉某个节点之后，最大的连通子图节点数
    st[u] = true; //标记访问过u节点
    int sum = 1; //存储 以u为根的树 的节点数, 包括u，如图中的4号节点

    //访问u的每个子节点
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        //因为每个节点的编号都是不一样的，所以 用编号为下标 来标记是否被访问过
        if (!st[j]) {
            int s = dfs(j);  // u节点的单棵子树节点数 如图中的size值
            res = max(res, s); // 记录最大联通子图的节点数
            sum += s; //以j为根的树 的节点数
        }
    }

    //n-sum 如图中的n-size值，不包括根节点4；
    res = max(res, n - sum); // 选择u节点为重心，最大的 连通子图节点数
    ans = min(res, ans); //遍历过的假设重心中，最小的最大联通子图的 节点数
    return sum;
}

int main() {
    memset(h, -1, sizeof h); //初始化h数组 -1表示尾节点
    cin >> n; //表示树的结点数

    // 题目接下来会输入，n-1行数据，
    // 树中是不存在环的，对于有n个节点的树，必定是n-1条边
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a); //无向图
    }

    dfs(1); //可以任意选定一个节点开始 u<=n

    cout << ans << endl;

    return 0;
}

Reference

[1]. yxc
[2]. 松鼠爱葡萄
[3]. 对邻接表存储细节的详解
[4]. Bug-Free
[5]. 最详细的题解–易懂
[6]. yx


树与图的广度优先遍历

847. 图中点的层次

基本思路

求最短距离，并且每条边的权重一样，所以可以用BFS

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstring>
#include <iostream>

using namespace std;

const int N=1e5+10;

int h[N], e[N], idx, ne[N];   //邻接表
int d[N]; //存储每个节点离起点的距离  d[1]=0
int n, m; //n个节点m条边
int q[N]; //手动模拟队列 


// 外部节点a, 邻接表的表头值b
void add(int a, int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int bfs()
{
    int hh=0,tt=0;

    q[0]=1; //队列初始化队头是1号节点

    memset(d,-1,sizeof d);

    d[1]=0; //存储每个节点离起点的距离

    //当我们的队列不为空时
    while(hh<=tt)
    {
        //取出队列头部节点
        int t=q[hh++];

        //遍历t节点的每一个邻接点
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            //如果j没有被搜索过
            if(d[j]==-1)
            {
                d[j]=d[t]+1; //d[j]存储j节点离起点的距离，并标记为访问过
                q[++tt] = j; //把j结点 压入队列
            }
        }
    }

    return d[n];
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }

    cout<<bfs()<<endl;
}

Reference

[1]. 847. 图中点的层次
[2]. 图中点的层次 详细注释
[3]. 真正本题需要实现的核心代码只有6句！
[4]. Bug-Free


拓扑排序

首先我们需要明确一个概念叫拓扑序列：一张图的所有边的前后关系可以用一个线性序列来简化表示（其实就是省略了一些边的信息）
那么这个线性序列就叫做该图的一个拓扑序列，一张图可能存在多个拓扑序列

如果图里存在还，就无法表示成线性序列，所以有环就没有拓扑序列

总结：

  1. 无向图，有向有还图没有拓扑序列，而有向无环图必然存在拓扑序列
  2. 拓扑序列只有从前向后的边，没有从后向前的边

848. 有向图的拓扑序列

基本思路

拓扑序列只有从前向后的边，没有从后向前的边

根据这个性质。我们只要每次放入队列的都是入度为0的点，那就一定满足都是从前向后的边

队列维护

  1. 将所有入度为0的点入队
  2. 删除这些点和他们的出边
  3. 循环上面的步骤
  4. 比较队列和图中点的数量

和BFS过程十分类似

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100010;
int h[N],e[N],ne[N],idx;
int n,m;
int q[N],d[N];//q表示队列,d表示点的入度

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];
            d[j]--;//删除点t指向点j的边
            if(d[j]==0)//如果点j的入度为零了,就将点j入队
            q[++tt]=j;
        }
    }
    return tt==n-1;
    //表示如果n个点都入队了话,那么该图为拓扑图,返回true,否则返回false
}

int main()
{
    cin>>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);//因为是a指向b,所以b点的入度要加1
        d[b]++;
    }
    if(topsort()) 
    {
        for(int i=0;i<n;i++)
        printf("%d ",q[i]);
        //经上方循环可以发现队列中的点的次序就是拓扑序列
        //注:拓扑序列的答案并不唯一,可以从解析中找到解释
        puts("");
    }
    else
    puts("-1");

    return 0;
}

Reference

[1]. yxc
[2]. E.lena
[3]. 思路介绍+图解模拟+详细代码注释
[4]. Bug-Free
[5]. 注释


最短路问题

最短路问题是图论里比较重要的篇章，下面简要的给单源最短路的相关算法的应用场景分一个类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
                                 |-------朴素dijkstra算法  O(n^2)
                                 |   
                                 |   
         |------所有边权都是正数---   
         |                       |
         |                       |
         |                       |-------堆优化的Dijkstra算法  O(mlogn)
单源最短路
         |                       |-------Bellman-ford  O(nm)
         |                       |
         |                       | 
         |-----存在负权边---------
                                 |
                                 |
                                 |-------SPFA   一般O(m), 最坏O(nm)

然后再介绍一下稠密图和稀疏图的概念：（n为点数，m为边数）
如果m和n是一个级别，那就是稀疏图，一般用邻接表来存
如果m和$n^2$是一个级别，那就是稠密图，一般用邻接矩阵来存

所以基本上SPFA可以解决 所有问题，但是有两个限制

  1. 如果对边数做了限制，那就只能用Bellman-ford
  2. 如果正权边的题目卡SPFA，把它变成了最坏情况O(mn),那就用Dijkstra算法

Dijkstra

849. Dijkstra求最短路 I

基本思路

图论的题目，首先都要看看数据范围，确定是稀疏图还是稠密图，然后选择合适的存储方式

这里m和n^2是一个级别，所以是稠密图，我们选择朴素的Dijkstra算法和邻接矩阵来存图

朴素的Digkstra算法基本流程如下：

1
2
3
4
5
6
//dis[i] 是i号节点到源点的距离，st为True表示在 S集合：存储当前已经确定最短距离的点)
1. 初始化dis[1] = 0, dis[i] = INF， st[1] = True
2. for i: i ~ n:          //n    
        t <-不在s中的距离源点最近的点   // O(n)
        s <- t        // O(1)
        用t更新其他点的距离    // O(n)

时间复杂度：$O(n^2)$

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=510;

int n,m;
int dist[N],g[N][N];//dist存储的是最短的距离,g存储的是邻接矩阵
bool st[N];//表示该点是否已经确定了最短距离

int dijkstra()
{
    memset(dist,0x3f,sizeof(dist));//初始化距离

    dist[1]=0;//起点到起点的距离为0

    for(int i=1;i<n;i++)//因为每次循环中都可以确定一个最短距离的点,因为总共有n个点,1这个点的距离已经确定了,所以循环n-1次
    {
        int t=-1;//t=-1的作用是可以找出第一个点
        for(int j=1;j<=n;j++)//第一轮循环,寻找与起点最短距离的点
        if(!st[j]&&(t==-1||dist[t]>dist[j]))
        t=j;

        st[t]=true;//标记该点的最短距离已经确定了,然后用确定的点更新其他点的最短距离

        for(int j=1;j<=n;j++)//第二轮循环,用已经确定了的最短距离的点来更新到其他点的最短距离
        dist[j]=min(dist[j],dist[t]+g[t][j]);
        //比较 起点到j的距离 和 起点到t的距离加上t到j的距离;
    }

    if(dist[n]==0x3f3f3f3f) return -1;//如果n到起点的距离为0x3f说明走不到n这个点
    //注:不能写成0x3f,只有清空操作时才能用0x3f,其他操作时需要写成0x3f3f3f3f,否则会报错
    else return dist[n];//返回起点到n的最短距离
}

int main()
{
    cin>>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);//可能存在重边,而本题追求的是最短距离,所以选择重边中最短的那条边
    }

    int t=dijkstra();

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

    return 0;

}

Reference

[1]. yxc
[2]. 超级详细的题解
[3]. E.lena
[4]. 两点小解释
[5]. 注意
[6]. 松鼠爱葡萄


850. Dijkstra求最短路 II

基本思路

还是先观察数据范围，这里m和n是一个级别，所以是稀疏图，我们选择堆优化的Dijkstra算法和邻接表来存图

堆优化的Digkstra算法基本流程如下：

1
2
3
4
5
1. 初始化dis[1] = 0, dis[i] = INF， st[1] = True
2. while(heap.size()):      
        t <-不在s中的距离源点最近的点(直接取小根堆的堆顶)  //总共n次，每次O(1), O(n)
        s <- t  // 总共n次，每次O(1), O(n)
        用t更新其他点的距离（更新需要将更新后的值插入堆里）   //最多m次，每次O(logn)手写堆 或者O(logm) 优先队列, 这两者只有常数级变化，O(mlogn)

时间复杂度：$O(mlogn)$

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#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;  //w表示权重
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;

    //小根堆的定义方式,PII的第一个变量存储的是距离,第二个变量存储的是该点的编号,
    //内部按照第一个变量排序,即按距离排序
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

    while (heap.size())
    {
        //1、找到当前未在s中出现过且离源点最近的点
        auto t = heap.top();
        heap.pop();

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

        if (st[ver]) continue;

        //2、将该点进行标记
        st[ver] = true;

        //3、用t更新其他点的距离
        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);
    }

    cout << dijkstra() << endl;

    return 0;
}

Reference

[1]. yxc
[2]. 小呆呆
[3]. 松鼠爱葡萄
[4]. E.lena
[5]. 深入理解st数组的作用
[6]. 使用stl邻接表
[7]. 用手写堆实现


Bellman-ford

853. 有边数限制的最短路

基本思路

有负权边，并且有边数限制，所以我们用Bellman-ford算法，基本流程如下

1
2
3
4
for k次 ：
    1. 备份
    2. for 所有边 a, b, w   a--w-->b    //遍历所有边 = 遍历所有点的出边(出边和邻接点是一一对应)
        dist[b] = min(dist[b], dist[a] + w);   //松弛

不管是有向图还是无向图，点的邻接点和点的出边是一一对应的！

循环结束后，对于所有边都满足三角不等式，dist[b] <= dist[a] + w
所以每个点都找到了最短距离

注意事项

  1. 备份是为了防止串联，串联后就有可能超出k的限制
  2. 最后答案可能为-1，所以不能用-1作为判断impossible的标识

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 510, M = 10010, INF = 0x3f3f3f3f;

int n, m, k;
int dist[N];
int backup[N];  // 备份数组，防止串联

struct Edges{
    int a, b, w;
}edges[M];

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

    dist[1] = 0;

    for (int i = 0; i < k; i ++ )
    {
        memcpy(backup, dist, sizeof dist);
        for (int j = 0; j < m ; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], backup[a] + w);
        }

    }

    if (dist[n] > INF / 2) return INF;
    else return dist[n];
}

int main()
{
    cin >> n >> m >> k;

    for (int i = 0; i < m; i ++ )
    {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }

    int t = bellman_ford();

    if (t == INF) puts("impossible");
    else cout << t << endl;

    return 0;
}

Reference

[1]. yxc
[2]. 松鼠爱葡萄
[3]. backup详解
[4]. 模拟
[5]. 问题汇总


SPFA

851. spfa求最短路

基本思路

SPFA其实是队列优化后的Bellman-ford算法，优化了松弛的步骤dist[b] = min(dist[b], dist[a]+w)
因为只有dist[a]更新之后变小, dist[b]更新之后才有可能变小
所以我们可以不用遍历所有点的出边，只需要遍历更新的点的出边即可

基本流程如下：

1
2
3
4
5
6
queue <-- 1
while queue非空
    1. t <-- q.front
        q.pop
    2. 更新t的所有出边 t--w-->b
        queue <--b

代码和堆优化的Dijkstra代码非常相似

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5+10, INF = 0x3f3f3f3f;

int n, m;  // n个点m条边
int h[N], e[N], w[N], ne[N], idx;  // 邻接表存储所有边
int dist[N]; // 存储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++;    
}

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;  // 初始化所有点的距离
    queue<int> q;  // 定义队列存储所有待更新的点
    q.push(1);  // 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];  // 找到出边，j存储编号
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];  //更新出边j的最短距离
                if(!st[j])  // 如果队列中已存在j，则不需将j重复插入
                {
                    q.push(j);  // 若j不在队列中，把j加入队列里
                    st[j] = true;  //标记该点在队列中
                }
            }
        }
    }
    if(dist[n] == INF) return INF;  // 1 ~ n不连通，返回-1
    return dist[n];  // 返回第n个点到源点的最短距离
}

int main()
{
    cin >> n >> m;
    // 构建邻接表
    memset(h, -1, sizeof h);  // 初始化所有表头
    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    int t = spfa();
    if(t == INF) puts("impossible");
    else cout << t << endl;
    return 0;
}

Reference

[1]. yxc
[2]. 队列优化的Bellman-Ford算法
[3]. 松鼠爱葡萄
[4]. Bug-Free
[5]. 分析
[6]. 图解+详细代码注释spfa求最短路−−−图解+详细代码注释


852. spfa判断负环

基本思路

这里是利用spfa来判断负环，加上一个cnt数组表示点到源点的最短距离的边数
如果cnt >= n 说明有边数大于节点数，必然有环，而且一定是负环

注意

  1. dist数组不用初始化，因为如果有负环，最终这些点的距离肯定是负无穷，所以不需要初始化
  2. 因为要判断的是图里是否存在负环，可能负环路径没有出现在源点上，所以一开始把所有的点入队

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#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;
}

Reference

[1]. yxc
[2]. 小呆呆
[3]. Bug-Free
[4]. 判断负环详解


Floyd

854. Floyd求最短路

基本思路

多源最短路问题，一般就是用Floyd算法，它是基于动态规划的思想

  1. 状态表示：f[k][i][j] 表示经过前k个点从i到j的距离
  2. 状态计算：f[k][i][j] = f[k - 1][i][j] + f[k - 1][k][j] //划分为不经过k和经过k两部分
  3. 省略k这个维度，因为它只和k - 1有关

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
using namespace std;

const int N = 210, M = 2e+10, INF = 1e9;

int n, m, k, x, y, z;
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() {
    cin >> n >> m >> k;
    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--) {
        cin >> x >> y >> z;
        d[x][y] = min(d[x][y], z);
        //注意保存最小的边
    }
    floyd();
    while(k--) {
        cin >> x >> y;
        if(d[x][y] > INF/2) puts("impossible");
        //由于有负权边存在所以约大过INF/2也很合理
        else cout << d[x][y] << endl;
    }
    return 0;
}

Reference

[1]. yxc
[2]. Floyd闫式dp分析法
[3]. Bug-Free
[4]. 文字性复习


最小生成树

关于生成树和最小生成树的定义
生成树：一个连通无向图的生成子图，同时要求是树。也即在n个点的图的边集中选择n - 1条，将所有顶点连通。
最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树

为了求解最小生成树，我们常用的有Prim算法和Kruskal算法

Prim

朴素Prim算法基本流程如下：

1
2
3
4
5
1. dist[i] = INF, dist[1]=0  //S集合存储当前已经确定在最小生成树里的点
2. for i in 0..n-1
      t <- 不在s中距离s最近的点
      s <- t
      用t更新其他点到s的距离

所以我们发现此算法跟Dijkstra算法非常相似
但是有一些区别：

  1. Dijkstra算法的t是距离源点最近的点，更新也是更新其他点到源点的距离
  2. 如果现在的距离为无穷大，那么说明没有最小生成树

858. Prim算法求最小生成树

基本思路

模板题，prim算法求解最小生成树,注意处理自环和重边

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

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


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

    int res = 0;
    for (int i = 0; i < n; i ++ )
    /* dijkstra是n - 1，是因为找到剩一个点时候，它不需要在计算了。而这里的n，
    最后剩一个点的时候，答案还是要加入边的，所以最后一个点必须实实在在的计算
    一遍所以迭代n次*/
    {
        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; // 返回最小生成树的边权重之和
}


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"); // 不存在生成树就输出 impossible，反之输出答案
    else printf("%d\n", t);

    return 0;
}

Reference

[1]. yxc
[2]. 课上详解
[3]. 边界条件和细节
[4]. Prim算法思想动图
[5]. 简要注释
[6]. 切分原理


Kruskal

859. Kruskal算法求最小生成树

基本思路

Kruskal算法流程:

1
2
3
4
1. 将所有边按照权重从小到大排序 O(mlog(m))
2. 枚举每条边(a, b， 权重c) O(m)
      if a, b 两点不连通
            将a, b边加入集合中

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

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

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; // 边数小于 n - 1，不存在最小生成树
    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;
}

Reference

[1]. yxc
[2]. 课上笔记详解
[3]. Kruskal算法思想gif图解
[4]. 朴素Prim算法+Kruskal算法
[5]. Bug-Free

算法 > AcWing
#算法 #图论
acwing算法笔记-图论
https://vendestine.com/map
Author
Wenzhe Li
Posted on
April 22, 2022
Licensed under