AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

常用代码模板3——搜索与图论

作者: 作者的头像   yxc ,  2019-07-31 21:51:16 ,  阅读 30923


170


364

算法基础课相关代码模板

  • 活动链接 —— 算法基础课

树与图的存储

树是一种特殊的图,与图的存储方式相同。
对于无向图中的边ab,存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储。

(1) 邻接矩阵:g[a][b] 存储边a->b

(2) 邻接表:

// 对于每个点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);

树与图的遍历

时间复杂度 $O(n+m)$, $n$ 表示点数,$m$ 表示边数

(1) 深度优先遍历 —— 模板题 AcWing 846. 树的重心

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);
    }
}

(2) 宽度优先遍历 —— 模板题 AcWing 847. 图中点的层次

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);
        }
    }
}

拓扑排序 —— 模板题 AcWing 848. 有向图的拓扑序列

时间复杂度 $O(n+m)$, $n$ 表示点数,$m$ 表示边数
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;
}

朴素dijkstra算法 —— 模板题 AcWing 849. Dijkstra求最短路 I

时间复杂是 $O(n^2+m)$, $n$ 表示点数,$m$ 表示边数
int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路,如果不存在则返回-1
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]))
                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];
}

堆优化版dijkstra —— 模板题 AcWing 850. Dijkstra求最短路 II

时间复杂度 $O(mlogn)$, $n$ 表示点数,$m$ 表示边数
typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
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];
}

Bellman-Ford算法 —— 模板题 AcWing 853. 有边数限制的最短路

时间复杂度 $O(nm)$, $n$ 表示点数,$m$ 表示边数

注意在模板题中需要对下面的模板稍作修改,加上备份数组,详情见模板题。

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];
}

spfa 算法(队列优化的Bellman-Ford算法) —— 模板题 AcWing 851. spfa求最短路

时间复杂度 平均情况下 $O(m)$,最坏情况下 $O(nm)$, $n$ 表示点数,$m$ 表示边数
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];
}

spfa判断图中是否存在负环 —— 模板题 AcWing 852. spfa判断负环

时间复杂度是 $O(nm)$, $n$ 表示点数,$m$ 表示边数
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;
}

floyd算法 —— 模板题 AcWing 854. Floyd求最短路

时间复杂度是 $O(n^3)$, $n$ 表示点数
初始化:
    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]);
}

朴素版prim算法 —— 模板题 AcWing 858. Prim算法求最小生成树

时间复杂度是 $O(n^2+m)$, $n$ 表示点数,$m$ 表示边数
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;
}

Kruskal算法 —— 模板题 AcWing 859. Kruskal算法求最小生成树

时间复杂度是 $O(mlogm)$, $n$ 表示点数,$m$ 表示边数
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;
}

染色法判别二分图 —— 模板题 AcWing 860. 染色法判定二分图

时间复杂度是 $O(n+m)$, $n$ 表示点数,$m$ 表示边数
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;
}

匈牙利算法 —— 模板题 AcWing 861. 二分图的最大匹配

时间复杂度是 $O(nm)$, $n$ 表示点数,$m$ 表示边数
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 ++ ;
}

78 评论


用户头像
Echo_j   1个月前     回复

y总,邻接表那里是头插法吗

用户头像
algsUP   1个月前     回复

是的,兄弟!

用户头像
Echo_j   1个月前    回复了 algsUP 的评论     回复

谢谢!


用户头像
zhangxj   1个月前     回复

请问能出一下优先级队列优化的prime算法吗

用户头像
yxc   29天前     回复

一般用不到,边数很大时Kruskal算法会更好写。


用户头像
激昂   4个月前     回复

堆优化版的dijkstra算法已经不能AC了......

用户头像
持续更新中   3个月前     回复

我还以为是Java最小堆的锅,误会解除

用户头像
Bulang   2个月前     回复

把N设成150010

用户头像
yxc   29天前     回复

应该是你错用了。


用户头像
Jocelyn   4个月前     回复

y总,为啥染色法要搜索有的点呢?如果是连通图的话 搜一个点不就遍历了整个图嘛

用户头像
掠风   3个月前     回复

因为可能不是连通图把 可能是由好几个连通图组成的图那这样做就行得通了

用户头像
yxc   29天前    回复了 掠风 的评论     回复

对滴。


用户头像
Doggie   5个月前     回复

y总 为什么spfa不需要0x3f3f3f3f/2呢 spfa不也有负权边吗 也可能最后成为0x3f3f3f3f+一个负数

用户头像
yxc   5个月前     回复

如果图不连通,那种终点一定不会被遍历到,则终点的dist一定是正无穷,不需要除以二。


用户头像
AnrolsP   5个月前     回复

y总, 为什么Dijikstra最短路的时候,用bellman算法求,还是必须要备份数组?

用户头像
yyfSoul   5个月前     回复

录像有讲的,用于防止新迭代和旧迭代之间距离存在更新串联。比如对于题设这个样例,在外循环k=1时(即最短路的长度是1),1到3的距离并不是2,而是∞。因此公式要引入backup

用户头像
AnrolsP   5个月前    回复了 yyfSoul 的评论     回复

em,我是想说,用bellman算法写dijkstra这道题 https://www.acwing.com/problem/content/solution/852/1/ (没有边数限制),只有加了backup才能求。

用户头像
yxc   5个月前    回复了 AnrolsP 的评论     回复

不加也是可以的,你应该是其他地方写错了。

用户头像
AnrolsP   5个月前    回复了 yxc 的评论     回复

确实是,删掉后备数组也可行,y总牛逼!

用户头像
shajunguang   4个月前    回复了 AnrolsP 的评论     回复

理解串了,因为bellman循环中前面的更新会引起后面更长边数的更新,因此使用backup保证边数递增

用户头像
yxc   4个月前    回复了 AnrolsP 的评论     回复

好滴。

用户头像
yxc   4个月前    回复了 shajunguang 的评论     回复

对滴。


用户头像
wisper   5个月前     回复

诶呀,太棒了

用户头像
yxc   5个月前     回复

谢谢hh


用户头像
沐   5个月前     回复

y总,邻接表中ne[], e[],h[] idx都是什么含义呀,学渣刚学。参考的单链表题链接404了呀

用户头像
Lemon_kk   5个月前     回复

ne是next指针 e存的节点值 h存表头 idx是节点编号(唯一)

用户头像
yxc   5个月前     回复

啊那个视频需要报名算法基础课之后才有权限。可以参考下这道题目:826. 单链表。这个是公开权限的。


用户头像
Hayasaka_   6个月前     回复

想问一下bellm - ford 算法这里外循环可不可以写成 0 -> n - 1 因为n个点最多只需要n - 1条边

用户头像
yxc   5个月前     回复

不可以,要判断负环的话至少要循环n层。

用户头像
Hayasaka_   5个月前    回复了 yxc 的评论     回复

懂了谢谢y总 如果不判负环的话n - 1可以嘛

用户头像
yxc   4个月前    回复了 Hayasaka_ 的评论     回复

可以的。

用户头像
Hayasaka_   4个月前    回复了 yxc 的评论     回复

谢谢y总 彻底懂了hh


用户头像
zxf   6个月前     回复

yxc,永远滴神!!!

用户头像
yxc   6个月前     回复

谢谢hh


用户头像
fedfan   7个月前     回复

spfa判断负环的这个注释好像有问题// dist[x]存储1号点到x的最短距离,cnt[x]存储1到x的最短路中经过的点数,
不一定是从1到x,起点不一定是1

用户头像
fedfan   7个月前     回复

这个到起点的距离可以不可以理解到虚拟节点的距离啊

用户头像
yxc   6个月前     回复

代码模板中默认1是起点,n是终点。

用户头像
fedfan   6个月前    回复了 yxc 的评论     回复

老师,可能是我之前表述不清楚,我的意思是在spfa 判断负环的时候,因为题目中没说连通,所以要把所有点加入队列,那这样求出来的cnt,dist的起点应该是每个联通块加的队列的起点吧

用户头像
yxc   6个月前    回复了 fedfan 的评论     回复

对的,不过这种表述太绕了。这种入队方式等价于先新建一个超级源点,然后从超级源点向每个点连一条长度是0的边。这样dist[]就表示每个点到超级源点的最短距离,cnt[]就表示最短路上的节点数量。

用户头像
fedfan   6个月前    回复了 yxc 的评论     回复

哦哦,谢谢y总


用户头像
zdw   11个月前     回复

赞,果断收藏

用户头像
yxc   11个月前     回复

很棒。


用户头像
Leo_Jose   12个月前     回复

老师,宽度优先遍历那个代码块的13行应该是
if(!st[j])而不是if(!s[j])把

用户头像
yxc   11个月前     回复

同学你是不是笔误了,这俩完全一样呀。

用户头像
stfst   11个月前    回复了 yxc 的评论     回复

不一样啊,st和s

用户头像
yxc   11个月前    回复了 stfst 的评论     回复

眼花了hh 多谢指正,已修正。


用户头像
Lemon_kk   12个月前     回复

为啥prim和dijkstra循环次数不一样,???

用户头像
yxc   11个月前     回复

算法很灵活,只要能保证正确即可,不用太纠结循环n次还是n-1一次。

用户头像
RobotOlivaw   10个月前     回复

是因为dijkstra最初将起始点加进了集合中的原因吧。

用户头像
yxc   10个月前    回复了 RobotOlivaw 的评论     回复

对滴。


用户头像
醒来   2020-01-27 06:05     回复

bellman-ford算法里面少了给backup数组

用户头像
yxc   2020-01-27 10:38     回复

一般情况下不需要使用backup数组,不影响结果的正确性。


用户头像
醒来   2020-01-18 14:13     回复

匈牙利算法里面有句注释好像错了,应该是从第一个集合指向第二个集合吧?
// 邻接表存储所有边,匈牙利算法中只会用到从第二个集合指向第一个集合的边,所以这里只用存一个方向的边

用户头像
yxc   2020-01-27 10:39     回复

多谢指正,已更正~


用户头像
xhQYm   2020-01-10 02:23     回复

邻接表中 ne[], e[] 是什么意思呀,蒟蒻刚学,麻烦了

用户头像
yxc   2020-01-13 15:21     回复

邻接表里用一个链表来表示一个点所有的邻点,ne是链表中的下一个点的下标,e是邻点的编号。

用户头像
yxc   2020-01-13 15:23     回复

可以参考AcWing 826. 单链表。


用户头像
greg666   2019-11-15 06:32     回复

猛然发现,模板总结跟我代码打卡的风格类似呀。

用户头像
yxc   2019-11-19 03:27     回复

很棒hh


用户头像
T-SHLoRk   2019-11-12 15:02     回复

为什么SPFA判断负环需要加入所有的节点进入队列呢?是为了防止负环和源点不在一个连通块么?

用户头像
yxc   2019-11-13 16:51     回复

对滴。


用户头像
Darron   2019-11-03 09:53     回复

y总,bellman-ford算法中模板是不是有问题啊,少了memcpy(backup, dist, sizeof dist);

用户头像
yxc   2019-11-03 13:53     回复

这里是没问题滴,一般的最短路问题中不需要备份距离数组,只有当有边数限制时才需要。

用户头像
T-SHLoRk   2019-11-12 13:37    回复了 yxc 的评论     回复

BellFord感觉本质上就是一个滚动数组的动态规划问题呀。不过模板没写backup但是模板题有个k,觉得这个还是提一句比较好。

用户头像
T-SHLoRk   2019-11-12 13:46    回复了 T-SHLoRk 的评论     回复

BTW,想问一下 BellFord算法里面为什么是判断dist[n] > 0x3f /2 ?而不是dist[n] = 0x3f

用户头像
yxc   2019-11-13 10:53    回复了 T-SHLoRk 的评论     回复

已在模板中提示。

用户头像
yxc   2019-11-13 10:55    回复了 T-SHLoRk 的评论     回复

因为存在负权边,所以当无解时dist[n]可能等于0x3f3f3f3f加上一个负权。


用户头像
一苇   2019-10-17 09:15     回复

Y神。prim与dijsktra 我有些混乱了

用户头像
yxc   2019-10-17 14:32     回复

好好理理,加油~

用户头像
一苇   2019-10-18 09:17    回复了 yxc 的评论     回复

今天再看 了然

用户头像
yxc   2019-10-19 05:15    回复了 一苇 的评论     回复

不错!

用户头像
一苇   2019-10-25 03:48    回复了 yxc 的评论     回复

y神 邻接表那部分加上初始化head为-1吧,一开始本渣渣没留意到这一点,一直超时,排查了好久 - -!!

用户头像
yxc   2019-10-28 11:19    回复了 一苇 的评论     回复

已加~


用户头像
Tell_me   2019-10-12 13:22     回复

y总,染色法判断二分图模板里面的dfs函数里的”int father”这个形参好像没起到作用啊。

用户头像
yxc   2019-10-14 14:53     回复

是的,已删除~


用户头像
烛之武   2019-08-02 01:54     回复

y总,时间复杂度应该加上

用户头像
yxc   2019-08-02 04:08     回复

已加~


用户头像
ZYzzz   2019-08-01 08:14     回复

赞赞赞赞赞赞赞赞!!!!!

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息