第8讲 最小生成树、最短路、关键路径

最小生成树

• 选出的总边权最小。

• 不一定唯一。

算法：

1. Prim：

1）朴素版，O(n2)，适合于稠密图，常用

2）堆优化，O(mlogn)，不一定比朴素版快。适合于稀疏图

   /*Prim：
从起始点开始当做一个集合，选附近一条边到该集合的最小距离加入该集合，不断
重复这个过程，知道所有点都加入到集合中，算法结束。
O(n2)
*/

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

using namespace std;

//N最大点数   M最多边数    
const int N = 510 , M = 100010 , INF = 0x3f3f3f3f;

//n点数 m边数
int n , m ;
//g图,邻接矩阵存储  dist当前集合内和集合外连接的每一个边的长度
int g[N][N] , dist[N];
//st标记每个点是不是在集合中
bool st[N];

//Prim
int Prim(){
    //dist数组距离初始化为正无穷
    memset(dist  , 0x3f , sizeof dist);
    //第一个点的距离设置0 ，同时进行选取
    dist[1] = 0 ;
    //答案表示当前的边权之和
    int res = 0;
    //遍历n个点
    for(int  i = 0; i < n ; i++){
        //t表示当前边权最小的点，就是集合外到集合内距离最小的点
        int t = -1 ; //初始为-1
        //枚举剩下的所有的点
        for(int j = 1 ; j <= n ; j++){
/*1.如果当前点没有在集合中  2.t还没有选过其他点 
  3.t选中的这个点不如当前这个点好（距离更优）
  t更新成当前点
*/
              if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        //如果当前的点都是正无穷的话，那就表示不连通，无解
        if(dist[t] == INF)  return INF ;
        //否则标记当前点已经遍历过
        st[t] = true;
        //更新答案，加入每次选取最小的边权
        res += dist[t];
        //枚举其他所有的点
        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--){
        //a点到b点之间的边权值为c
        int a , b , c;
        scanf("%d%d%d" , &a , &b , &c);
        //注意是无向图，所以是对称的.如果有重边，选取最小的
        g[a][b] = g[b][a] = min(g[a][b] , c);

    }
    //res答案
    int res = Prim();
    //无解
    if(res == INF) puts("impossible");
    else printf("%d" , res);  //输出答案

    return 0;
}

1. Kruskal（O(mlogn)）：常用

   /*kruskal：
每次选一条最小的边，不构成环，直到所有的点都选中。
*/

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

using namespace std;

//N最大点数   M最多边数    
const int N = 510 , M = 100010 , INF = 0x3f3f3f3f;

//n点数 m边数
int n , m ;

//边
struct Edge{
    //a , b两个端点 ，c表示权值
    int a , b , c;
    //定义比较函数
    bool operator< (const Edge& t) const {
        return c < t.c;
    }
}e[M];

//并查集
int p[N];

//并查集的找组成元素？  
int find(int x)  // 并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}


int main(){
    scanf("%d%d" , &n , &m);
    //读入所有的边
    for(int i = 0 ; i < m ; i++){
        scanf("%d%d%d" , &e[i].a , &e[i].b , &e[i].c);
    }

    //把每条边按照权值大小进行排序
    sort(e , e + m);
    //初始化并查集的代表元素？
    for(int i = 1 ; i <= n ; i++) p[i] = i;
    //res答案  cnt连通块的数量，一开始是n个
    int res = 0 , cnt = n;
    //枚举所有的边
    for(int i = 0 ; i < m ; i++){
        //取出边的信息
        int a  = e[i].a , b = e[i].b , c = e[i].c;
        //判断当前两个点不在一个连通块内，那就把当前的边加入进来
        if(find(a) != find(b)){
            //更新答案,连通块数量减减，同时把这两个合并到同一个连通块里
            res += c;
            cnt--;
            p[find(a)] = p[find(b)];
        }
    }
    //如果连通块大于1，不存在生成树
    if(cnt > 1) puts("impossible");
    else printf("%d\n" , res);  //输出答案

    return 0;
}

最短路

一般是有向图，但是无向图可以看做是特殊的有向图，即在建边的时候两点之间构成环即可。

1. 单源最短路 Dijkstra（不能求负权边的最短路径）：
2. 只有一个起点到其他所有点的最短路
3. 分情况：
   • 无负权边
   • 朴素Dijkstra O(n2)：稠密图
   • （不考）堆优化Dijkstra O(mlogn） ：稀疏图
   • 有负权边（不考，略过）
   • Bellman-Ford O(nm)
   • SPFA（Bellman的宽搜优化） O(m)

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

using namespace std;

//定义最大点数N 最多边数M 正无穷
const int N = 510 , M = 100010 , INF = 0x3f3f3f3f;

//点数n 边数m
int n , m;
//邻接矩阵存稠密图   dist存每个点到起点的最短距离
int g[N][N] ,dist[N];

//用于在更新最短距离时 判断当前的点的最短距离是否确定 是否需要更新
bool st[N];


int dijkstra(){
    //先把距离初始化为正无穷
    memset(dist , 0x3f , sizeof dist);
    //起点的距离是0
    dist[1] = 0;
    //枚举所有的点
    for(int i  = 0 ; i < n ; i++){
        //t表示当前距离最小 的点,一开始设为-1
        int t = -1;
        //再枚举所有的点
        for(int j = 1 ; j <= n ; j++){
            //当前点没有确定距离  t是-1或者t的距离（上一个点）大于j（当前点）的距离
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j; //t更新为当前的点
        }
        //标记t已经被遍历过
        st[t] = true;
        //再用t这个点更新到其他点的距离
        for(int j = 1 ; j<= n ;j ++){
            dist[j] =  min(dist[j] , dist[t] + g[t][j]);
        }
    }
    //返回最短路径
    return dist[n];
}

int main(){
    scanf("%d%d" , &n , &m);
    //初始化所有的边权，一开始不连通设为正无穷，后面会慢慢更新
    memset(g , 0x3f , sizeof g);
    while(m--){//读入m条边
        //一条边的两个端点和权值
        int a  ,b ,c;
        scanf("%d%d%d" , &a , &b , &c);
        //可能会有重边，取最小值
        g[a][b] = min(g[a][b] , c);
    }
    //求距离
    int res = dijkstra();
    //距离为正无穷，输出-1，无解
    if(res == INF) puts("-1");
    else printf("%d\n" , res);

    return 0;
}

1. 多源汇最短路 Floyd O(n3)：
2. 有多个起点和终点，求任意两点之间的最短路径

关键路径

1. AOE网，拓扑图，点时间，边活动（有大于0 的权值），有前后关系（个人理解：若一个点有多个箭头指向它，那么那些箭头必须在这个点之前完成，这样才能到达这个点，拓扑排序也是这样的。）

2. 最长的一条路径，关键路径不一定唯一，但没有环。

（下面两个概念很懵。。暂时放在这。。。。。）

1. 事件（点）最早开始时间：从起点开始看到这个点的最长时间

事件最晚·开始时间：不延期的情况下，关键路径减掉从终点到这个点的最长路径。

活动（边）最早开始时间：就是事件最早开始时间（不确定。。。。）

活动最晚开始时间：（不确定。。。。。。）

1. 关键事件：事件最早=事件最晚

关键活动：活动最早=活动最晚

考题：

2011-41、2012-7、2012-8、2013-9、2015-6、2015-42、2016-8、2017-42、2018-42、2019-5、2020-7、2020-8

1. 判断dijkstra序列的点顺序：按照权值（最短距离）严格递增去排序结点即可
2. 最小生成树不唯一，但是最小生成树代价唯一，注意辨别。
3. 邻接矩阵A2计算，按照数学里面的矩阵运算即可。A2元素值表示：从 i 点到 j 点长度为2的有多少种走法。