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

作者： 作者的头像   yxc ,  2019-07-31 21:51:16 ,  所有人可见 ,  阅读 121704

601


938

算法基础课相关代码模板

树与图的存储

树是一种特殊的图，与图的存储方式相同。
对于无向图中的边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 ++ ;
}

140 评论

用户头像
认真学习   1个月前      5    踩      回复

y总什么时候出Java版的模板啊

用户头像
thunderclouds   2天前         踩      回复

y总估计短时间内出不了的, 可以取对应模板题下面找java同学的代码, 也大差不差的了

用户头像
Repeater   4个月前      1    踩      回复

为啥染色法时间复杂度不是nm而是n + m?

用户头像
wt20   4个月前      1    踩      回复

怎么可能是nm呢....

用户头像
Repeater   4个月前    回复了 wt20 的评论         踩      回复

循环里面套一个递归啊，循环是n递归是m

用户头像
wt20   4个月前    回复了 Repeater 的评论         踩      回复

要知道那个循环一共循环m次啊....

用户头像
wt20   4个月前    回复了 Repeater 的评论         踩      回复

就像bfs 为什么是O(n)一样....

用户头像
天郁闷   3个月前         踩      回复

因为每个点只会遍历和它有关的边，边数一共是m条，点数一共是 n个，所以时间复杂度是: $O(n + m)$

用户头像
LeRoi   1个月前         踩      回复

图的dfs是不回溯的吧

用户头像
邹晧   1个月前         踩      回复

为啥不

用户头像
LeRoi   1个月前    回复了 邹晧 的评论         踩      回复

我说的y总写的模板，回溯的话要看具体题目吧

用户头像
邹晧   1个月前    回复了 LeRoi 的评论         踩      回复

ok
回溯的话要看具体题目吧（所以……

用户头像
chesseur   1个月前         踩      回复

y总的 bellman_ford

#include<bits/stdc++.h>

using namespace std;

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

int st[N];
int n,m,k;

int dist[N];
int backup[N];


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

int bellman_ford()
{
    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;
            if(dist[b]>backup[a] +w)
            {
                dist[b] = backup[a] +w;
            }
        }
    }
    return  dist[n];
}


int main()
{
    memset(dist,0x3f,sizeof dist);
    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);
//      g[x][y]= min(g[x][y],z);
        edges[i] = {x,y,z};
    }
    int ans = bellman_ford();
    if(ans >=INF>>1 ) //  避免正常返回的-1 
    {
        printf("impossible\n");
    }
    else{
        printf("%d\n",ans);
    }
    return 0;
}
用户头像
纯纯正能量   1个月前         踩      回复

y总以前还来看看评论，现在都不来看了

用户头像
纯纯正能量   1个月前         踩      回复

我知道他不会来的（dog）

用户头像
yxc   1个月前    回复了 纯纯正能量 的评论      5    踩      回复

会滴。

用户头像
纯纯正能量   1个月前    回复了 yxc 的评论      1    踩      回复

哈哈

用户头像
aaaaw   2个月前         踩      回复

yxc yyds

用户头像
srq_conan   5个月前         踩      回复

堆优化版Prim算法（能过859题）

#include<algorithm>
#include<bitset>
#include<cctype>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<deque>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<vector>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef vector <int> vi;
const int MAXN=1e5+5, MAXM=4e5+5;
const int INF=0x3f3f3f3f;

int idx, head[MAXN], to[MAXM], Next[MAXM], w[MAXM];
int n, m, dist[MAXN];
bool st[MAXN];

void add(int u, int v, int we)
{
    to[idx]=v;
    w[idx]=we;
    Next[idx]=head[u];
    head[u]=idx++;
}

int prim()
{
    int res=0, cnt=0;
    priority_queue <pii, vector<pii>, greater<pii> > q;
    memset(dist, 0x3f, sizeof(dist));
    dist[1]=0;
    q.push({0, 1});
    while (q.size())
    {
        pii t=q.top();
        q.pop();
        int id=t.second;
        if (st[id])
            continue;
        st[id]=true;
        cnt++;
        res+=dist[id];
        for (int i=head[id]; ~i; i=Next[i])
        {
            int j=to[i];
            if (w[i]<dist[j])
            {
                dist[j]=w[i];
                q.push({dist[j], j});
            }
        }
    }
    return cnt==n?res:INF;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(head, -1, sizeof(head));
    for (int i=0; i<m; i++)
    {
        int u, v, we;
        scanf("%d%d%d", &u, &v, &we);
        add(u, v, we);
        add(v, u, we);
    }
    int res=prim();
    if (res==INF)
        printf("impossible\n");
    else
        printf("%d\n", res);
    return 0;
}
用户头像
Expelliarmus2011   4个月前         踩      回复

这么多头文件，为什么不用bits/stdc++.h

用户头像
fuchsine   4个月前    回复了 Expelliarmus2011 的评论         踩      回复

这是人家用的比较习惯的模板，放在编译器的预定义宏文件里了，每次都会自动打开，就不用每次都敲一遍了

用户头像
达不溜了   1个月前    回复了 fuchsine 的评论         踩      回复

个人感觉要什么就加什么，这样看的真的头疼

用户头像
lgc576   6个月前         踩      回复

为什么匈牙利算法最大匹配那道题不能用邻接表存储，代码如下：

#include <iostream>
#include <cstring>

using namespace std;
const int N = 510, M = 100010;
int n1, n2, m;
int g[N][N], match[N];
bool st[N];

bool find(int x){
    for(int j = 1; j <= n2 && g[x][j]; j++)
    {
        if(!st[j])
        {
            st[j] = true;
            if(!match[j] || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

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

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

    int res = 0;
    for(int i = 1; i <= n1; i++)
    {
        memset(st, false , sizeof st);
        if(find(i)) res++;
    }

    printf("%d", res);

    return 0;
}
用户头像
中指半仙   6个月前         踩      回复

az，没啥区别啊

用户头像
lgc576   6个月前    回复了 中指半仙 的评论         踩      回复

其实这代码不知道哪里有误运行起来会结果不一样，疑惑在于结果不正确

用户头像
acwing_8111   5个月前    回复了 lgc576 的评论         踩      回复

判断g[x][j] == 1要移到下面if(g[x][j] && !st[j])

用户头像
lgc576   5个月前    回复了 acwing_8111 的评论         踩      回复

大佬我懂了，要把所有另一方遍历一遍，放在上面会提前终止，谢谢

用户头像
317   6个月前         踩      回复 
NB
用户头像
不到130不改名   7个月前         踩      回复

朴素dijkstra算法为啥是 n^2 + m呢，为啥要加m而不是n^2呢？

用户头像
每根头发都有名字   5个月前         踩      回复

m可能比n^2大

用户头像
天郁闷   5个月前         踩      回复

因为最后一个循环实际上是遍历了所有边，如果你在一个稀疏图中使用朴素版dijkstra,时间复杂度就是边数决定的

用户头像
Cloud_   7个月前         踩      回复

y总yyds

用户头像
Taurus_   7个月前         踩      回复

重温

用户头像
l-zx   7个月前         踩      回复

谢谢算法让我感受y总的美

用户头像
Chace_Q   7个月前         踩      回复

啊草，哈哈哈哈哈哈哈哈哈哈

用户头像
CodeSlogan   7个月前         踩      回复

y总yyds

用户头像
AvariceZhao   7个月前         踩      回复

邻接表不懂的可以看下这个视频BV14o4y1d7vv

用户头像
AvariceZhao   7个月前         踩      回复

在视频最后有通过一组数据讲解邻接表存图

用户头像
小孙   9个月前         踩      回复

邻接表里存的是每条边吗

用户头像
码   8个月前         踩      回复

对,h[a]代表点a到其他点的边

用户头像
ikaqiu   11个月前         踩      回复

请问在树与图的遍历-（2）宽度优先遍历中使用的是queue队列
为什么在循环的时候使用的是e[i]和ne[i]呢

用户头像
卓杯   11个月前         踩      回复

这是用邻接表存的边，当然要用邻接表的方法来遍历该点（此时的队列头）能到达的点了

用户头像
ikaqiu   10个月前    回复了 卓杯 的评论         踩      回复

喔喔，我以为直接用队列存下来的，大意了，谢谢你

用户头像
levelna   11个月前         踩      回复

day6初见图

用户头像
ZCPUZZLE   12个月前         踩      回复

谢谢美让算法感受y总之美

用户头像
See   2021-09-10 06:26         踩      回复

谢谢y算让我感受总法之美