头像

小张睡不醒




离线:3小时前


最近来访(33)
用户头像
惊蛰_0
用户头像
straySheep.
用户头像
wqsh
用户头像
Amaryllis_
用户头像
jwh
用户头像
不高兴的兽奶
用户头像
ray_
用户头像
谈笑起_2
用户头像
寄一心明月
用户头像
晶晶吖
用户头像
163.com
用户头像
incra
用户头像
云衣醉梦
用户头像
浅笑_36
用户头像
970545464473
用户头像
Would
用户头像
Foraino0267
用户头像
吃小孩
用户头像
小颂
用户头像
brianxi

分享 动态规划

1.背包问题
(1)01背包,每个物品只有一个f[i][j]=max(f[i-1][j],f[i-1][j-v]+w)
(2)完全背包 每个物品无限使用f[i][j]=max(f[i-1][j],f[i][j-kv]+kw)
(3)完全背包 每个物品有多个 f[i][j]=max(f[i][j],f[i-1][j-kv[i]]+kw[i]);数多:(先化组,在看成01背包)
(4)分组背包 每组物品有若干个,同一组内的物品最多只能选一个。



分享 数学知识

欧几里得算法 —— 模板题 AcWing 872. 最大公约数

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

快速幂
m的k次方mol p

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


分享 二分图


二分图:图中点通过移动能分成左右两部分,左侧的点只和右侧的点相连,右侧的点只和左侧的点相连。

染色法

看成树,一层0一层1,如果不符合不是二分图
1. 对每个点进行染色
2. 枚举该点的所有出边到达的点,染上不一样的颜色
3. 如果存在奇数环,就不存在二分图
dfs版本
       代码思路:
       染色可以使用1和2区分不同颜色,用0表示未染色
       遍历所有点,每次将未染色的点进行dfs, 默认染成1或者2
       由于某个点染色成功不代表整个图就是二分图,因此只有某个点染色失败才能立刻break/return
       染色失败相当于至少存在2个点染了相同的颜色

染色法判别二分图 —— 模板题 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;
}

题目描述
给定一个 n 个点 m 条边的无向图,图中可能存在重边和自环。

请你判断这个图是否是二分图。

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行,每行包含两个整数 u 和 v,表示点 u 和点 v 之间存在一条边。

输出格式
如果给定图是二分图,则输出 Yes,否则输出 No。

数据范围
1≤n,m≤105
样例
4 4
1 3
1 4
2 3
2 4
输出
Yes

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

using namespace std;

const int N = 100010 * 2;
int e[N], ne[N], idx;//邻接表存储图
int h[N];
int color[N];//保存各个点的颜色,-1未染色,1 是红色,2 是黑色
int n, m;//点和边

void add(int a, int b)//邻接表插入点和边
{
    e[idx] = b, ne[idx]= h[a], h[a] = idx++;
}

bool dfs(int u, int c)//深度优先遍历
{
    color[u] = c;//u的点成 c 染色

    //遍历和 u 相邻的点
    for(int i = h[u]; i!= -1; i = ne[i])
    {
        int b = e[i];                   
        if(color[b]==-1)//相邻的点没有颜色,则递归处理这个相邻点
        {
            if(!dfs(b, 3 - c)) return false;//(3 - 1 = 2, 如果 u 的颜色是2,则和 u 相邻的染成 1)
                                            //(3 - 2 = 1, 如果 u 的颜色是1,则和 u 相邻的染成 2)
        }
        else if( color[b] == c)//如果已经染色,判断颜色是否为 3 - c
        {                                     
            return false;//如果不是,说明冲突,返回                   
        }
    }
    return true;
}

int main()
{
    memset(h, -1, sizeof h);//初始化邻接表
    cin >> n >> m;
    for(int i = 1; i <= m; i++)//读入边
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    memset(color, -1, sizeof color);
    for(int i = 1; i <= n; i++)//遍历点
    {
        if(color[i]==-1)//如果没染色
        {
            if(!dfs(i, 1))//染色该点,并递归处理和它相邻的点
            {
                cout << "No" << endl;//出现矛盾,输出NO 
                return 0;
            }

        }
    }
    cout << "Yes" << endl;//全部染色完成,没有矛盾,输出YES
    return 0;
}

匈牙利算法(求最大匹配)

思路
如果你想找的妹子已经有了男朋友,
你就去问问她男朋友,
你有没有备胎,
把这个让给我好吧


匈牙利算法 —— 模板题 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 ++ ;
}

题目描述
给定一个二分图,其中左半部包含 n1 个点(编号 1∼n1),右半部包含 n2 个点(编号 1∼n2),二分图共包含 m 条边。

数据保证任意一条边的两个端点都不可能在同一部分中。

请你求出二分图的最大匹配数。

二分图的匹配:给定一个二分图 G,在 G 的一个子图 M 中,M 的边集 {E} 中的任意两条边都不依附于同一个顶点,则称 M 是一个匹配。

二分图的最大匹配:所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配,其边数即为最大匹配数。

输入格式
第一行包含三个整数 n1、 n2 和 m。

接下来 m 行,每行包含两个整数 u 和 v,表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边。

输出格式
输出一个整数,表示二分图的最大匹配数。

数据范围
1≤n1,n2≤500,
1≤u≤n1,
1≤v≤n2,
1≤m≤105

样例
输入样例:
2 2 4
1 1
1 2
2 1
2 2
输出样例:
2

#include<bits/stdc++.h>

using namespace std;

const int N = 510, M = 100010;

int n1,n2,m;
int h[N],e[M],ne[M],idx;
int match[N];
bool st[N];

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

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 main()
{
    cin>>n1>>n2>>m;

    memset(h,-1,sizeof h);

    //建立邻接表
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }

    //表示匹配数
    int res=0;

    //枚举每一个男生
    for(int i=1;i<=n1;i++)
    {
        //把女生全部考虑一遍
        memset(st,0,sizeof st);

        if(find(i)==true) res++;
    }

    cout<<res<<endl;

    return 0;
}





微信图片_20230127131848.jpg

生成树:一个来连通图的最小连通子图,n个顶点的连通图有n个顶点n-1个边
最小生成树就是权值最小的数
树是所有的点连通,图是点到点。
prim稠密图,Kruskal算法稀疏图
不过Kruskal算法yyds都适用

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

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

大佬链接
https://www.acwing.com/solution/content/38312/
微信图片_20230127134331.jpg

朴素版prim算法 —— 模板题 AcWing 858. Prim算法求最小生成树
时间复杂度是 O(n2+m), n 表示点数,m 表示边数
确定一个点找与它相连的最短边,和Dijkstra思路一样
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 表示边数

Kruskal算法 —— 模板题 AcWing 859. Kruskal算法求最小生成树
时间复杂度是 O(mlogm), n 表示点数,m 表示边数
先把边排序,挨个找最小边,用到了并查集
1. 将每条边从小到大排序
2. 枚举每条边,如果不在一个集合就合并集合
3. res 表示最小生成树权重之和
4. cnt 表示已加入集合的边数
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;
}

prim

联系:Dijkstra算法是更新到起始点的距离,Prim是更新到集合S的距离
与dijkstra一样只是在距离的时候一个+到起始点的距离一个没有。

题目描述
给定一个n个点m条边的无向图,图中可能存在重边和自环,边权可能为负数。

求最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。

给定一张边带权的无向图G=(V, E),其中V表示图中点的集合,E表示图中边的集合,n=|V|,m=|E|。

由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树,其中边的权值之和最小的生成树被称为无向图G的最小生成树。

输入格式
第一行包含两个整数n和m。

接下来m行,每行包含三个整数u,v,w,表示点u和点v之间存在一条权值为w的边。

输出格式
共一行,若存在最小生成树,则输出一个整数,表示最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。

数据范围
1≤n≤500,
1≤m≤105,
图中涉及边的边权的绝对值均不超过10000。

输入样例:
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例:
6

#include<bits/stdc++.h>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

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

int prim()
{
    memset(dist,0x3f,sizeof dist);//初始化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[j]<dist[t]))
                t=j;

        if(i!=0&&dist[t]==INF) return INF;//,最近的点无穷说明点不连通,直接返回INF
        if(i!=0) 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()
{
    cin>>n>>m;

    memset(g,0x3f,sizeof g);

    //邻接矩阵,取较小边
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=g[b][a]=min(g[a][b],c);
    }
    int t=prim();//用t提前存储,防止prim()运行两次
    if(t==INF) cout<<"impossible"<<endl;
    else cout<<t<<endl;

    return 0;
}

Kruskal

大佬连接
https://www.acwing.com/solution/content/104383/

算法思路:

将所有边按照权值的大小进行升序排序,然后从小到大一一判断。

如果这个边与之前选择的所有边不会组成回路,就选择这条边分;反之,舍去。

直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。

筛选出来的边和所有的顶点构成此连通网的最小生成树。

判断是否会产生回路的方法为:使用并查集。

在初始状态下给各个个顶点在不同的集合中。、

遍历过程的每条边,判断这两个顶点的是否在一个集合中。

如果边上的这两个顶点在一个集合中,说明两个顶点已经连通,这条边不要。如果不在一个集合中,则要这条边。

#include<iostream>
#include<cstring>
#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;//res权重之和cnt多少边
    for(int i=0; i<m; i++)
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;


        if(find(a)!=find(b))//判断两者是否连通,若不连通则
        {
            p[find(a)] = find(b);//两个集合合并
            res += w;//res加的是,最小生成树边的权重之和
            cnt++;//当前加入多少边
        }
    }

    if(cnt < n-1) return INF;//判断一共加了多少条边,若是cnt小于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);

}



https://www.acwing.com/solution/content/6976/
负环和回路的影响:邻接表没有影响,邻接矩阵,初始化0x3f,用点求距离
,在DJ里面是点来求距离,可以忽略,spfa优先队列,忽略,ford忽略,
多源里面不能忽略,先排除自环(不存在负权回路)

Dijkstra-朴素 O(n2)O(n2)
1.初始化距离数组, dist[1] = 0, dist[i] = inf;
2.for n次循环 每次循环确定一个min加入S集合中,n次之后就得出所有的最短距离
3.将不在S中dist_min的点->t
4.t->S加入最短路集合
5.用t更新到其他点的距离
Dijkstra-堆优化 O(mlogm)O(mlogm)
1.利用邻接表,优先队列
2.在priority_queue<PII,vector<PII>,greater<PII>> heap;中将返回堆顶
3.利用堆顶来更新其他点,并加入堆中类似宽搜
Bellman_ford O(nm)O(nm)
注意连锁想象需要备份, struct Edge{int a,b,c} Edge[M];
1.初始化dist, 松弛 dist[x.b] = min(dist[x.b], backup[x.a]+x.w);
2.松弛k次,每次访问m条边
Spfa O(n)∼O(nm)O(n)∼O(nm)
1.利用队列优化仅加入修改过的地方
2.for k次
3.for 所有边利用宽搜模型去优化bellman_ford算法
4.更新队列中当前点的所有出边
Floyd O(n3)O(n3)
1.初始化d
2.k, i, j 去更新d

spfa已死 只要是正权边就会卡成Bellman-Ford




微信图片_20230125140235.jpg

spfa判断负环

判断负环的时候都放进去,不一定从那个点开始,五个点有四条边--当边数>=n的时候一定有负环。
spfa判断图中是否存在负环 —— 模板题 AcWing 852. spfa判断负环
时间复杂度是 O(nm)O(nm), nn 表示点数,mm 表示边数
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算法

floyd算法 —— 模板题 AcWing 854. Floyd求最短路
时间复杂度是 O(n3), 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]);
}

题目描述
题目描述
给定一个 nn 个点的有向图,请求出图中是否存在从顶点 11 出发能到达的负环。

负环的定义是:一条边权之和为负数的回路。

输入格式
本题单测试点有多组测试数据。

输入的第一行是一个整数 TT,表示测试数据的组数。对于每组数据的格式如下:

第一行有两个整数,分别表示图的点数 nn 和接下来给出边信息的条数 mm。

接下来 mm 行,每行三个整数 u, v, w。

若 w \geq 0w≥0,则表示存在一条从 u 至 vv边权为 ww的边,还存在一条从 v 至 u 边权为 w 的边。
若 w < 0w<0,则只表示存在一条从 u 至 vv 边权为 w 的边。
输出格式
对于每组数据,输出一行一个字符串,若所求负环存在,则输出 YES,否则输出 NO。

样例
输入:
2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8

输出

NO
YES

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int w[N];
int dist[N], cnt[N];//记录每个点到起点的边数,当cnt[i] >= n 表示出现了边数>=结点数
//,必然有环,而且一定是负环!
bool st[N];//判断当前的点是否已经加入到队列当中了;
//意味着,st数组起着提高效率的作用,不在乎效率的话,去掉也可以
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;
    // 这里不需要初始化dist数组为 正无穷。不用初始化的原因是,如果存在负环那么dist不管初始化为多少都会被更新
    //定义队列,起点进队, 标记进队
    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();
        //t出队,标记出队
        st[t] = false;

        //更新与t邻接的边
        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];//结点j可以通过中间点t降低距离
                cnt[j] = cnt[t] + 1;//那么结点j在中间点t的基础上加一条到自己的边

                if (cnt[j] >= n) return true;//边数不小于结点数,出现负环,函数结束

                if (!st[j])//若此时j没在队列中,则进队。已经在队列中了,上面已经更新了数值。重复加入队列降低效率
                {
                    //j进队,标记进队
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;//走到这了,函数还没结束,意味着边数一直小于结点数,不存在负环
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

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


    return 0;
}

floyd算法

floyd算法 —— 模板题 AcWing 854. Floyd求最短路
时间复杂度是 O(n3), n 表示点数
初始化:
d[N][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;
    或者
    memset(d,INF,sizeof d);
    for(int i=1;i<=n;i++)d[i][i]=0;

// 算法结束后,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]);
}

给定一个n个点m条边的有向图,图中可能存在重边和自环,边权可能为负数。
再给定k个询问,每个询问包含两个整数x和y,表示查询从点x到点y的最短距离,如果路径不存在,则输出“impossible”。
数据保证图中不存在负权回路。

输入格式
第一行包含三个整数n,m,k
接下来m行,每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。
接下来k行,每行包含两个整数x,y,表示询问点x到点y的最短距离。

输出格式
共k行,每行输出一个整数,表示询问的结果,若询问两点间不存在路径,则输出“impossible”。

数据范围
1≤n≤200,
1≤k≤n^2
1≤m≤20000,
图中涉及边长绝对值均不超过10000。

输入样例:
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例:
impossible
1
#include<bits/stdc++.h>

using namespace std;

const int N = 210, INF = 0x3f3f3f3f;

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()
{
    cin>>n>>m>>q;
    memset(d,0x3f,sizeof d);//初始化d数组
    for(int i=1;i<=n;i++) d[i][i]=0;//防止自环,取最小数0,
    while(m--) //邻接矩阵,取权值较小的边
    {
        int a,b,c;
        cin>>a>>b>>c;
        d[a][b]=min(d[a][b],c);
    }

    floyd();

    while(q--)
    {
        int a,b;
        cin>>a>>b;

        if(d[a][b]>INF/2) cout<<"impossible"<<endl;
        else cout<<d[a][b]<<endl;
    }

    return 0;
}




SPFA也可以在都是正权值使用,怕时间复杂度卡,最大O(mn)
二者可以判断负环,但存在负环不求最短路。
ford存在负环的时候可以用边数作为限制剔除负环的影响

 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];//存边要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 ++ )//n为次数
    {
        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算法

spfa 算法(队列优化的Bellman-Ford算法) —— 模板题 AcWing 851. spfa求最短路
时间复杂度 平均情况下 O(m)O,最坏情况下 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];
}

用更新的点更新其他点
1. 初始化dist数组和队列q
2. st表示该点在队列中,用于提速
3. 取出队头,更新该点的所有出边,如果可以更新就放到队列中


# 判断负环

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


   dist[b] = min(dist[b], backup[a] + w);
注意:back[] 数组是上一次迭代后 dist[] 数组的备份,由于是每个点同时向外出发,因此需要对 dist[] 数组进行备份,若不进行备份会因此发生串联效应,影响到下一个点
1. 迭代 k 次就可以得到不经过 k 次的最短路
2. 要准备 backup 数组,这样就会只更新当前点能到达的所有点,就不会发生串联效应
3. 注意:INF - 1 < INF, 但 INF + 1 == INF
4. 因为有负权边,所以只需判断 bellman_ford() >= INF / 2 即可

ford

给定一个 n 个点 m条边的有向图,图中可能存在重边和自环, 边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离,如果无法从 1 号点走到 n 号点,输出 impossible。

注意:图中可能 存在负权回路 。

输入格式
第一行包含三个整数 n,m,k。

接下来 mm 行,每行包含三个整数 x,y,zx,y,z,表示存在一条从点 xx 到点 yy 的有向边,边长为 zz。

点的编号为 1∼n。

输出格式
输出一个整数,表示从 1 号点到 nn号点的最多经过 k条边的最短距离。

如果不存在满足条件的路径,则输出 impossible。

数据范围
1≤n,k≤500,
1≤m≤10000,
1≤x,y≤n1≤x,y≤n,
任意边长的绝对值不超过 10000。

输入样例:
3 3 1
1 2 1
2 3 1
1 3 3
输出样例:
3
思路:
Bellman-Ford基本过程,有k的限制必须使用Ford算法

#include<iostream>
#include<cstring>

using namespace std;

const int N = 510, M = 10010;

struct Edge {
    int a;
    int b;
    int w;
} e[M];//把每个边保存下来即可
int dist[N];
int back[N];//备份数组防止串联
int n, m, k;//k代表最短路径最多包涵k条边

int bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < k; i++) {//k次循环
        memcpy(back, dist, sizeof dist);
        for (int j = 0; j < m; j++) {//遍历所有边
            int a = e[j].a, b = e[j].b, w = e[j].w;
            dist[b] = min(dist[b], back[a] + w);
            //使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
        }
    }
    if (dist[n] > 0x3f3f3f3f / 2) return -1;//注意为0x3f/2;有负环可能趋近于无穷;
    else return dist[n];

}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        e[i] = {a, b, w};
    }
    int res = bellman_ford();
    if (res == -1) puts("impossible");
    else cout << res;

    return 0;
}

spfa

spfa求最短路正权图也可以.

spfa 算法(队列优化的Bellman-Ford算法) —— 模板题 AcWing 851. spfa求最短路
时间复杂度 平均情况下 O(m)O,最坏情况下 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];
}

用更新的点更新其他点
1. 初始化dist数组和队列q
2. st表示该点在队列中,用于提速
3. 取出队头,更新该点的所有出边,如果可以更新就放到队列中

题目描述
给定一个n个点m条边的有向图,图中可能存在重边和自环, 边权可能为负数。

请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出impossible。

数据保证不存在负权回路。

输入格式
第一行包含整数n和m。

接下来m行每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。

输出格式
输出一个整数,表示1号点到n号点的最短距离。

如果路径不存在,则输出”impossible”。

数据范围
1≤n,m≤105,
图中涉及边长绝对值均不超过10000。

输入样例:
3 3
1 2 5
2 3 -3
1 3 4

输出样例:
2

#include<bits/stdc++.h>
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; //起点距自己的距离为 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]) //更新 t 的所有邻边
        {
            int j = e[i]; //取出当前邻边的节点,在这步消除了重边
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j]) //如果 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;
}



微信图片_20230125140235.jpg

一个图中,顶点数n,边数m,当n^2>>m,为稀疏–堆优化m–n)一个级别(100 100)邻接表
当m相对较大时为稠密图。*朴素的*(m–n^2)一个级别(100 10000)邻接矩阵
不超过k条边,BELLMAN
单源只有一个起点,到其他点的最短路
多源 多个点的最短路

朴素dijkstra算法

详细的推到
https://www.acwing.com/solution/content/38318/

朴素dijkstra算法 —— 模板题 AcWing 849. Dijkstra求最短路 I
时间复杂是 O(n2+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 ++ )//n次迭代,每次寻找不在s中距离最近的点t
    {
        int t = -1;     //不存在负值所以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]);//g[t][j]就是节点t可以到的路径里面最小值

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

Dijkstra求最短路 I
题目描述
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 −1。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式
输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出 −1。

数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。

输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3

单源且均为正值用Dijkstra算(m,n^2),
1.
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];//邻接矩阵
int dist[N];//1号点到其他点的距离
bool st[N];//st[i], 第i个点是否确定, 归入s集合中

int dijkstra(){
    memset(dist, 0x3f, sizeof dist);//初始化所有点到一号点的距离为正无穷
    dist[1] = 0;//初始化第一个点到自己的距离是0

    for(int i = 0; i < n - 1; i++)//迭代n - 1次
    {
        int t = -1;//t = -1表示还没有点, t: 不在集合s中的离一号点距离最近的点
        for(int j = 1; j <= n; j++)//找到不在集合s中与一号点距离最近的点
            if(!st[j] && (t == -1 || dist[t] > dist[j]))//如果j不在集合s中且 (还没有点或者当前t这个点不是离一号点最短的点)
                t = j;
        //执行完之后t就是不在集合s中距离一号点最近的点
        st[t] = true;//把t存入集合s中

        for(int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);//本来应该是用t更新
            //其他不在集合s中的点的距离
        //但是这里直接用t更新全部点的距离,这是因为已经确定距离的点不会受t的影响。
        //因为dist[j] = min(dist[j], dist[t] + g[t][j]);
        //对于已经确定了最短距离的点dist[j] <= dist[t]恒成立,这是由t的定义决定的
        //对于t 和 j这两个点,j 是比 t 先确定最短距离的点,因此dist[j]一定小于dist[t] 
        //况且dist[t]还要加一个g[t][j]那么这个值就更大了
    }

    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}
int main()
{
    scanf("%d%d", &n, &m);//读入点数和边数
    //存在重边和自环,重边的话保留最短的一条就行了,自环直接忽略掉

    memset(g, 0x3f, sizeof g);//初始化点与点之间的距离为正无穷 包括自己到自己也是正无穷
    //这里不必纠结自己到自己的距离是0还是正无穷因为只有在用t更新时 j = t才会用到g[t][t]自己到自己的距离,且dist[t] = min(dist[t], dist[t] + g[t][t])
    //从公式可以看出g[t][t] = 0或正无穷dist[t]都不变
    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;
}

2.
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int g[N][N];    //为稠密阵所以用邻接矩阵存储
int dist[N];    //用于记录每一个点距离第一个点的距离
bool st[N];     //用于记录该点的最短距离是否已经确定
int n,m;
int Dijkstra()
{
    memset(dist, 0x3f,sizeof dist);     //初始化距离  0x3f代表无限大
    dist[1]=0;  //第一个点到自身的距离为0
    for(int i=0;i<n;i++)      //有n个点所以要进行n次 迭代
    {
        int t=-1;       //t存储当前访问的点
        for(int j=1;j<=n;j++)   //这里的j代表的是从1号点开始
            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]);//g[t][j]就是t点到其他的距离
    }

    if(dist[n]==0x3f3f3f3f) return -1;  //如果第n个点路径为无穷大即不存在最低路径
    return dist[n];
}
int main()
{
    cin>>n>>m;

    memset(g,0x3f,sizeof g);    //邻接矩阵的初始化,由于求的是最小值,因此初始为无穷大
    while(m--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        g[x][y]=min(g[x][y],z);     //如果发生重边的情况则保留最短的一条边
    }

    cout<<Dijkstra()<<endl;
    return 0;
}

2.稀疏图–>邻接表
给定一个 nn 个点 mm 条边的有向图,图中可能存在重边和自环,所有边权均为非负值。

请你求出 11 号点到 nn 号点的最短距离,如果无法从 11 号点走到 nn 号点,则输出 −1−1。

输入格式
第一行包含整数 nn 和 mm。

接下来 mm 行每行包含三个整数 x,y,zx,y,z,表示存在一条从点 xx 到点 yy 的有向边,边长为 zz。

输出格式
输出一个整数,表示 11 号点到 nn 号点的最短距离。

如果路径不存在,则输出 −1−1。

数据范围
1≤n,m≤1.5×1051≤n,m≤1.5×105,
图中涉及边长均不小于 00,且不超过 1000010000。
数据保证:如果最短路存在,则最短路的长度不超过 109109。

输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3
思路
这题和 Dijkstra求最短路IDijkstra求最短路I 思路是一样的,就是把枚举选哪个点改成用优选队列来维护最短的长度,还要把迭代换成优先队列是否为空即可。
用堆来优化,就是优化点更新

#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;//ver:节点编号,distance:源点距离ver 的距离

        if (st[ver]) continue;//如果距离已经确定,则跳过该点
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])//更新ver所指向的节点距离
        {
            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;
}


分享 拓扑排序

思路:

1. 看这个图是否有环,如果没有环就一定存在拓扑序列
2. 求出每个点的入度
3. 把所有入度为 0 的点入队
4. 枚举每一条边,删除它就是让 d[j] --;
5. 当入度为 0 时,说明前面的点都已经有序,将当前点入队
6. 当所有点都入队时说明存在拓扑序列
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;
}

微信图片_20230124135219.jpg
题目描述
给定一个 n 个点 m 条边的有向图,点的编号是 1 到 n,图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 −1。

若一个由图中所有点构成的序列 A 满足:对于图中的每条边 (x,y),x 在 A 中都出现在 y 之前,则称 A 是该图的一个拓扑序列。

样例
3 3
1 2
2 3
1 3
输出
123

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,m;
int h[N],e[N],ne[N],idx;
int q[N],d[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++)//把所有入度为0的点入队
        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]--;//入度减一
            if(d[j]==0)
            q[++tt]=j;
        }
    }

    //当所有点入队时,说明存在拓扑序列
    return tt==n-1;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    //建边,并且b的入度加1
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        d[b]++;//a->b所以b的入度加一
    }

    //若为真,说明所有点都已入队
    if(topsort())
        for(int i=0;i<n;i++)
            cout<<q[i]<<' ';
    else cout<<-1<<endl;

    return 0;
}

2.STL

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = N;
int n, m;
int h[N], e[M], ne[M], idx;
int d[N];  //入度
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void topsort() {
    queue<int> q;
    int ans[N], top = 0;
    for (int i = 1; i <= n; i++)
        if (!d[i]) q.push(i), ans[++top] = i;
    while (q.size()) {
        int t = q.front(); q.pop();
        for (int i = h[t]; ~i ; i = ne[i]) {
            int j = e[i];
            if (--d[j] == 0) q.push(j), ans[++top] = j;
        }
    }
    if (top != n) puts("-1");
    else for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
}


int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    while (m--) {
        int a, b; scanf("%d%d", &a, &b);
        add(a, b); d[b]++;
    }
    topsort();
    return 0;
}




树与图的存储
树是一种特殊的图,与图的存储方式相同。
对于无向图中的边ab,存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储。
(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)O(n+m), nn 表示点数,mm 表示边数
(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);
    }
}

微信图片_20230123144227.jpg

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

题目描述
给定一颗树,树中包含n个结点(编号1~n)和n-1条无向边。

请你找到树的重心,并输出将重心删除后,剩余各个连通块中点数的最大值。

重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。

输入格式
第一行包含整数n,表示树的结点数。

接下来n-1行,每行包含两个整数a和b,表示点a和点b之前存在一条边。

输出格式
输出一个整数m,表示重心的所有的子树中最大的子树的结点数目。

数据范围
1≤n≤105

样例
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例:
4
652_ab4f9f7c9b-1.png


结论
在本题的邻接表存储结构中,有两个容易混淆的地方,一个是节点的编号,一个是节点的下标。
节点的编号是指上图所画的树中节点的值,范围是从1~n。在本题中,每次输入的a和b就是节点的编号,编号用e[i]数组存储。
节点的下标指节点在数组中的位置索引,数组之间的关系就是通过下标来建立连接,下标用idx来记录。idx范围从0开始,如果idx==-1表示空。
1:->4->7->2
2:->5->8->1
e[i]的值是编号,是下标为i节点的编号,如例1:e[0]=4,e[1]=7,e[2]=2。
ne[i]的值是下标,是下标为i的节点的next节点的下标,e[0]=2,e[1]=3;e[3]=-1。
h[i]存储的是下标,是编号为i的节点的next节点的下标,比如编号为1的节点的下一个节点是4,那么我输出e[h[1]]就是4h[1]=0,e[h[1]]=4;

#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++;//插在头节点,a为根可以到的点,最前面,不同于链表比较方便
}

// dfs 框架
/*
void dfs(int u){
    st[u]=true; // 标记一下,记录为已经被搜索过了,下面进行搜索过程
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j]) {
            dfs(j);
        }
    }
}
*/

//返回以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];//用e[i]来存储节点的数值,取出来
        if (!st[j]) {//因为每个节点的编号都是不一样的,所以 用编号为下标 来标记是否被访问过
            int s = dfs(j);  // u节点的单棵子树节点数 如图中的size值
            res = max(res, s); // 记录最大联通子图的节点数,就是取出u以后两个的最大值
            sum += s; //以j为根的树 的节点数
        }
    }

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

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

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

    dfs(1); //可以任意选定一个节点开始 u<=n。选择的节点,不是位置

    cout << ans << endl;

    return 0;
}

树与图的广度优先遍历

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

题目描述(图中点的层次)
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环。

所有边的长度都是 1,点的编号为 1∼n。

请你求出 1 号点到 n 号点的最短距离,如果从 1 号点无法走到 n 号点,输出 −1。

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行,每行包含两个整数 a 和 b,表示存在一条从 a 走到 b 的长度为 1 的边。

输出格式
输出一个整数,表示 1 号点到 n 号点的最短距离。

数据范围
1≤n,m≤105

输入样例
4 5
1 2
2 3
3 4
1 3
1 4

输出样例
1

微信图片_20230124134635.jpg

1.模拟数组
#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]; //存储层次遍历序列 0号节点是编号为1的节点

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; //0号节点是编号为1的节点,可以换点,是拉链法换对头

    memset(d,-1,sizeof d);//先初始化,在赋值d[n]=0;要不然少一。

    d[1]=0; //存储每个节点离起点的距离 从1号节点开始,距离为0,从2开始,d[2]=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;
}
2.stl
#include<iostream>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;

const int N=1e5+10;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N];

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

int bfs()
{
    memset(d,-1,sizeof d);宽搜模板,如果换点就换对头,d[x]=0,也改变
    queue<int> q;
    d[1]=0;
    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(d[j]==-1)
            {
                d[j]=d[t]+1;
                q.push(j);
            }
        }
    }
    return d[n];
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    printf("%d ",bfs());
    return 0;
}
2.模板
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int e[N],ne[N],h[N],d[N],idx;
int m,n;
bool st[N];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs()
{
    queue<int>q;
    q.push(1);
    st[1]=true;
    memset(d,-1,sizeof d);
    d[1]=0;
    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])
            {
                d[j]=d[t]+1;
                st[j]=true;
                q.push(j);
            }
        }
    }
    return d[m];

}
int main()
{
    cin>>m>>n;
    memset(h,-1,sizeof h);
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    printf("%d",dfs());
    return 0;
}