AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 问答
    • 吐槽
  • App
  • 登录/注册

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

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


750


1163

算法基础课相关代码模板

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

树与图的存储

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

153 评论


用户头像
偶遇   2021-08-01 09:41      69    踩      回复

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

用户头像
Payxtl   2021-08-04 11:38         踩      回复

你是魔鬼吗哈哈哈哈哈

用户头像
knighz   2021-08-04 18:59         踩      回复

what the ....

用户头像
泠翎子   2021-08-08 16:31         踩      回复

???

用户头像
自由基   2021-08-09 08:47         踩      回复

hhhhh

用户头像
哈哈哈哈啊哇哇哇   2021-08-13 21:38         踩      回复

疯了,抬走

用户头像
林小胖   2021-08-14 09:45         踩      回复

y总确实很美

用户头像
thehun   2021-08-16 22:17         踩      回复

这位更是重量级

用户头像
琴叶榕   2021-09-11 22:58    回复了 thehun 的评论         踩      回复

这位更是个寄吧

用户头像
无名_00   2022-01-02 08:58         踩      回复

xswl

用户头像
Evander.Liam   2022-03-18 09:46         踩      回复

???

用户头像
_Dream_   5个月前      1    踩      回复

位更寄

用户头像
dingxi   4个月前         踩      回复

建议加大药量

用户头像
L-China   2个月前         踩      回复

魔鬼哦

用户头像
超长轨道b   2个月前         踩      回复

牛


用户头像
认真学习   7个月前      6    踩      回复

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

用户头像
thunderclouds   6个月前      2    踩      回复

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


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

算法可视化
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html


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

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

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

我知道他不会来的(dog)

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

会滴。

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

哈哈


用户头像
pxzwy   54分钟前      1    踩      回复

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


用户头像
Zh0uKal1   2个月前      1    踩      回复

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


用户头像
chesseur   7个月前      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;
}

用户头像
啥也不会hh   10个月前      1    踩      回复

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

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

怎么可能是nm呢....

用户头像
啥也不会hh   10个月前    回复了 wt20 的评论         踩      回复

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

用户头像
wt20   10个月前    回复了 啥也不会hh 的评论         踩      回复

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

用户头像
wt20   10个月前    回复了 啥也不会hh 的评论      1    踩      回复

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

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

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


用户头像
爱玩牌的dream   2个月前         踩      回复

这个会不会也有”spfa”版本的算法求最小生成树


用户头像
不是早晨就是黄昏   3个月前         踩      回复

朴素版dijkstra算法的第一层循环不是从i = 0; i < n吗,为啥上面写的是i = 0; i < n - 1,这样就不是n层循环了吧


用户头像
歌姬葛平   5个月前         踩      回复

拓扑排序 输入创建邻接表的时候,忘了更新入度了?


用户头像
Royal_Never_Give_Up   5个月前         踩      回复
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);
    }
}

y总这里的int不应该改为void吗


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

图的dfs是不回溯的吧

用户头像
Coding-Dream   7个月前         踩      回复

为啥不

用户头像
LeRoi   7个月前    回复了 Coding-Dream 的评论         踩      回复

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

用户头像
Coding-Dream   7个月前    回复了 LeRoi 的评论         踩      回复

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


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

yxc yyds


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

堆优化版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   10个月前         踩      回复

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

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

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

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

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

用户头像
了虐别   3个月前    回复了 fuchsine 的评论         踩      回复

咋加啊

用户头像
了虐别   3个月前         踩      回复

什么是堆优化啊

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

我也觉得hhh


用户头像
lgc576   2022-03-10 10:19         踩      回复

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

#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;
}
用户头像
中指半仙   2022-03-25 13:27         踩      回复

az,没啥区别啊

用户头像
lgc576   2022-03-26 22:13    回复了 中指半仙 的评论         踩      回复

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

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

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

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

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


用户头像
317   2022-03-07 15:16         踩      回复
NB

用户头像
不到130不改名   2022-02-19 14:19         踩      回复

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

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

m可能比n^2大

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

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


用户头像
Kiki_   2022-02-18 10:50         踩      回复

y总yyds


用户头像
Taurus_   2022-02-09 23:23         踩      回复

重温


你确定删除吗?
1024
x

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