3. 基础搜索与图论初识

浪漫主义狗

发布于 2022-07-11 08:40:21

4930

发布于 2022-07-11 08:40:21

文章被收录于专栏：HAUE_LYS'BlogHAUE_LYS'Blog

3.1 简单搜索

分类

DFS
BFS
A* (BFS+贪心)
双向广搜
双端队列广搜
双向DFS
IDDFS (DFS+BFS)
IDA* (IDDFS优化)

3.1.1 BFS

思想

当题目需要对一组数据进行扩展式搜索时可以考虑BFS
搜索时要将已经满足要求的点入队
不断地弹出队头，以队头元素进行扩展搜索，可以得到若干新的元素
对这些元素进行判断，满足继续搜索的条件则将该元素入队，否则具体问题具体分析，标记或抛弃。
一般来说，BFS在第一次搜到答案时可以直接返回值，提前结束搜索

例题 844. 走迷宫

原题链接

描述

给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。

数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。

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

接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

输出格式 输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围 1≤n,m≤100 输入样例：

输出样例：

代码

#include <bits/stdc++.h>
using namespace std;

const int N=110;

int mp[N][N];  //记录地图

bool vis[N][N];  //标记该点是否走过

int ans[N][N];  //存储答案

int n,m;

struct point{  //初始化point为struct类型
    int x,y;
};

int dx[]={0,0,1,-1},dy[]={1,-1,0,1};

int bfs(){

    queue<point> st;  //定义队列
    st.push({1,1});  //将起始点的信息入队
    vis[1][1]=1;  //标记起始点已经走过

    while(!st.empty()){

        auto p=st.front();  //使p获得队头的信息
        st.pop();  //将队头出队

        for(int i=0;i<4;i++){  //循环遍历偏移量数组，搜索四个方向

            int l=p.x+dx[i],r=p.y+dy[i];
            if(l>=1&&l<=n&&r>=1&&r<=m&&mp[l][r]==0&&!vis[l][r]){   //判断该点是否满足搜索条件
                ans[l][r]=ans[p.x][p.y]+1;  //更新答案
                if(l==n&&r==m) return ans[n][m];  //搜到答案直接返回
                vis[l][r]=1;  //标记该点已经走过
                st.push({l,r});  //将该点入队，后续继续扩展该点搜索
            }

        }

    }

    return ans[n][m];  //没有提前搜到答案，最后返回答案

}

int main(){

    cin>>n>>m;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
        }
    }

    cout<<bfs()<<endl;

    return 0;

}

例题走出迷宫

原题链接

描述

小明现在在玩一个游戏，游戏来到了教学关卡，迷宫是一个N*M的矩阵。

小明的起点在地图中用“S”来表示，终点用“E”来表示，障碍物用“#”来表示，空地用“.”来表示。障碍物不能通过。小明如果现在在点（x，y）处，那么下一步只能走到相邻的四个格子中的某一个：（x+1，y），（x-1，y），（x，y+1），（x，y-1）；

小明想要知道，现在他能否从起点走到终点。

输入格式: 本题包含多组数据。每组数据先输入两个数字N,M 接下来N行，每行M个字符，表示地图的状态。

数据范围： 2<=N,M<=500 保证有一个起点S，同时保证有一个终点E.

输出格式: 每组数据输出一行，如果小明能够从起点走到终点，那么输出Yes，否则输出No

输入样例：

3 3
S..
..E
...
3 3
S##
###
##E

输出样例

Yes
No

分析

走出迷宫需要对每一个点进行搜索
首先需要记录S的坐标
从S开始搜索，需要偏移量数组
对于BFS在搜随时，若搜到E点直接返回

BFS代码

#include <bits/stdc++.h>
using namespace std;

const int N=510;

int n,m;

char mp[N][N];  //存储地图

bool vis[N][N];  //标记是否走过该点

int s1,s2;  //标记S的坐标

int dx[]={0,0,1,-1},dy[]={1,-1,0,0};  //初始化偏移量数组

struct point{  //用于记录点的信息
    int x,y;
};

bool bfs(){

    queue<point> st;  //定义队列

    st.push({s1,s2});  //将S点的信息入队
    vis[s1][s2]=1;  //标记S点为走过

    while(!st.empty()){  //当队列不空时

        auto p=st.front();  //使p获得队头的信息
        st.pop();  //将队头出队

        for(int i=0;i<4;i++){  //循环遍历偏移量数组，搜索四个方向

            int l=p.x+dx[i],r=p.y+dy[i];
            if(l>=1&&l<=n&&r>=1&&r<=m&&!vis[l][r]&&mp[l][r]!='#'){  //判断该点是否满足搜索条件
                if(mp[l][r]=='E') return 1;  //搜到答案直接返回
                vis[l][r]=1;  //标记该点已经走过
                st.push({l,r});  //将该点入队，后续继续扩展该点搜索
            }

        }

    }

    return 0;

}

int main(){

    while(cin>>n>>m){

        //初始化清空数据
        memset(vis,0,sizeof vis);
        memset(mp,0,sizeof mp);

        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>mp[i][j];
                if(mp[i][j]=='S'){  //标记S的坐标
                    s1=i;
                    s2=j;
                }
            }
        }

        if(bfs()) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;

    }

    return 0;

}

3.1.2 DFS

思想

利用递归，将大问题拆分为同类型的小问题解决
一般情况下，从初识状态出发，进行扩展得到若干新的状态
选定一个状态继续深入，直到不再出现新的状态为止，然后回退，并将上一层的状态恢复
重复上述过程，直到将所有可以达到的状态全部遍历
一般来说，使用DFS在提前搜索到答案时一般只进行标记，不提前返回或退出
当搜索过程中出现明显不满足目标的状态时可以提前返回，减少搜索次数

例题 3429. 全排列

原题链接

描述

给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。

我们假设对于小写字母有 a<b<…<y<z，而且给定的字符串中的字母已经按照从小到大的顺序排列。

输入格式 输入只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在 1 到 6 之间。

输出格式 输出这个字符串的所有排列方式，每行一个排列。

要求字母序比较小的排列在前面。

字母序如下定义：

已知 S=s1s2…sk,T=t1t2…tk，则 S<T 等价于，存在 p(1≤p≤k)，使得 s1=t1,s2=t2,…,sp−1=tp−1,sp<tp 成立。

数据范围 字符串的长度在 1 到 6 之间

输入样例：

abc

输出样例：

abc
acb
bac
bca
cab
cba

分析

对于全排列，我们需要明确排列的顺序,按照字典序排列分析
递归处理，每一次递归视为一次选择，递归的层数即为选择数
对于每一次的选择进行标记，记录选择并递归到下一层
回退时要对上一次的标记的状态进行还原

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+3;

char a[N];  //存入可选的字符
char ans[N];  //存储当前的排列

bool vis[N];  //记录是否选过了该字符

int n;

void dfs(int u){

    if(u==n){  //当选够了全部的字符

        for(int i=0;i<n;i++){  //遍历输出排列
            cout<<ans[i];
        }
        cout<<endl;
        return ;

    }

    for(int i=0;i<n;i++){
        if(!vis[a[i]]){  //若该字符未曾使用
            vis[a[i]]=1;  //标记为使用过
            ans[u]=a[i];  //选择该字符加入排列
            dfs(u+1);  //递归到下一层
            vis[a[i]]=0;  //恢复状态
        }
    }

}

int main(){

    cin>>a;  //读入字符数组

    n=strlen(a);  //得到该字符数组的长度

    dfs(0);

    return 0;

}

例题 843. n-皇后问题

原题链接

描述

n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

现在给定整数 n，请你输出所有的满足条件的棋子摆法。

输入格式 共一行，包含整数 n。

输出格式 每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

注意：输出顺序要按照样例的规律

数据范围 1≤n≤9 输入样例：

输出样例：

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

分析

由于皇后不能互相攻击到，故棋盘的每一行，每一列及其有皇后存在的对角线的平行线上有且只有一个皇后
递归处理，每一次递视为一次对棋子的判断，递归的层数视为棋盘的层数，每一层选择放置一个皇后
对于递归的每一层，遍历这层棋盘的格子，判断以该格子的列和对角线的平行线上是否存在过皇后
若放置皇后，则需要对放置的格子所在的列和对角线的平行线进行标记，并将其记录在答案数组中
递归处理上述过程，直到将皇后放置完毕，此时遍历答案数组输出一次排列
对于对角线的处理，我们可以利用数学关系，转换为截距进行标记

代码

#include <bits/stdc++.h>
using namespace std;

const int N=100;

int n;

char mp[N][N];  //当前棋盘的状态

bool y[N],l[N],r[N];  //标记是否存在过皇后

void dfs(int u){

    if(u==n+1){  //当u=n+1时说明第n层的棋盘已经放置完毕，输出一次可能性

        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cout<<mp[i][j];
            }
            cout<<endl;
        }
        cout<<endl;
        return ;
    }

    for(int i=1;i<=n;i++){

        if(!y[i]&&!l[u-i+n]&&!r[u+i+n]){  //若该点所在的列及其所在的对角线的平行线不曾出现过皇后
            y[i]=l[u-i+n]=r[u+i+n]=1;  //标记
            mp[u][i]='Q';  //放置皇后
            dfs(u+1);  //递归到下一层
            mp[u][i]='.';  //回溯
            y[i]=l[u-i+n]=r[u+i+n]=0;
        }

    }

}

int main(){

    cin>>n;

    for(int i=1;i<=n;i++){  //初始化
        for(int j=1;j<=n;j++){
            mp[i][j]='.';
        }
    }

    dfs(1);

    return 0;

}

3.2 树与图的深度优先遍历

思想

通过邻接表建图
利用DFS进行遍历

例题 846. 树的重心

原题链接

描述

给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1 条无向边。

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

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

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

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

输出格式 输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围 1≤n≤105 输入样例

输出样例：

代码

#include <bits/stdc++.h>
using namespace std;

int n;

const int N=1e6+3;

int ans=0x3f3f3f3f;

int h[N],e[N],ne[N],idx;  //初始化邻接表

bool vis[N];  //记录是否走过了该节点

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;  //建图过程
}

//返回以u为根的子树中节点的数量
int dfs(int u ){

    vis[u]=1;  //标记走过了该节点

    int size=0,sum=1;  //size记录子树节点数量的最大值，sum用于记录根子树的个数

    for(int i=h[u];i!=-1;i=ne[i]){  //dfs遍历子树结点

        if(!vis[e[i]]){

            int s=dfs(e[i]);
            size=max(size,s);
            sum+=s;

        }

    }

    size=max(size,n-sum-1);  //n-sum表示的是减掉u为根的子树，整个树剩下的点的数量
    ans=min(ans,size);   //遍历过的假设重心中，最小的最大联通子图的节点数

    return sum;

}

int main(){

    memset(h,-1,sizeof h);  //初始化邻接表的表头，-1表示尾节点

    cin>>n;

    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);  //建立无向图，a->b b->a
    }

    dfs(1);

    cout<<ans<<endl;

    return 0;

}

3.3 树与图的广度优先遍历

思想

通过邻接表建图
利用BFS进行遍历

例题 847. 图中点的层次

原题链接

描述

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。

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

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

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

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

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

数据范围 1≤n,m≤105 输入样例：

输出样例：

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+3;

int n,m;

int h[N],e[N],ne[N],idx;  //初始化邻接表

bool vis[N];  //记录是否走过了该节点

int dist[N];  //记录1号点到n号点的距离

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;  //建图过程
}

int bfs(){

    memset(dist,-1,sizeof dist);  //初始化1号点到n号点的距离全为-1
    dist[1]=0;  //1号点到1号点的距离为0

    queue<int> st;  //初始化队列
    st.push(1);  //1号点入队
    vis[1]=1;  //标记为走过

    while(!st.empty()){

        int p=st.front();
        st.pop();

        for(int i=h[p];i!=-1;i=ne[i]){  //遍历邻接表

            if(!vis[e[i]]){

                vis[e[i]]=1;
                dist[e[i]]=dist[p]+1;  //距离+1
                st.push(e[i]);

            }

        }

    }

    return dist[n];

}

int main(){

    memset(h,-1,sizeof h);   //初始化邻接表的表头，-1表示尾节点

    cin>>n>>m;

    for(int i=0;i<m;i++){

        int a,b;
        cin>>a>>b;
        add(a,b);  //建立有向图 a->b

    }

    cout<<bfs()<<endl;

    return 0;

}

3.4拓扑排序

概念

拓扑序列是对于有向图而言的，有向图的拓扑序是其顶点的线性排序

对于上图，存在4条边：（1,3）（1,2）（2,4）（2,3）
该图的拓扑序必须要满足以下两点：
1. 每个顶点只出现一次。
2. 对于图中的任何一条边，起点必须在终点之前。

判断是否是拓扑序

一个有向图，如果图中有入度为 0 的点(没有其他点指向该点)，就把这个点删掉，同时也删掉这个点所连的边
重复上述处理，如果所有点都能被删掉，则这个图可以进行拓扑排序

以上图为例：

初始图为上图的状态，发现1的入度为 0，所以删除1和1上所连的边，结果如下图：

此时发现2的入度为 0，3的入度为 0，所以删除2和2上所连的边、3和3上所连的边，结果如下图：

此时发现4的入度为 0，且4为最后一个节点，按照删除的顺序可以得到拓扑序

注意：只有有向无环图才有拓扑序，所以有向无环图又被称为拓扑图。

例题 848. 有向图的拓扑序列

描述

给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。

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

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

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

接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。

输出格式 共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

否则输出 −1。

数据范围 1≤n,m≤105 输入样例：

输出样例：

1 2 3

分析

首先用邻接表建图，同时记录各个点的入度
调用BFS时将入度为 0 的点放入队列
将队列里的点依次出队列，然后找出所有出队列这个点发出的边，删除边，更新被删掉边的节点的入度
如果所有点都进过队列，则可以拓扑排序，输出所有顶点。否则输出-1，代表不可以进行拓扑排序

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+3;

int n,m;

int h[N],e[N],ne[N],idx;  //初始化邻接表

int cnt[N];  //记录每个点的入度

queue<int> ans;  //记录删掉的节点即为一种答案

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;  //建图过程
}

bool bfs(){

    queue<int> st;  //初始化队列

    for(int i=1;i<=n;i++){  //将入度为 0 的点放入队列
        if(cnt[i]==0){
            st.push(i);
        }
    }

    while(!st.empty()){

        int p=st.front();
        st.pop();

        for(int i=h[p];i!=-1;i=ne[i]){

            cnt[e[i]]--;  //删掉该边
            if(cnt[e[i]]==0){  //删掉边后入度变为0，则将其入队
                st.push(e[i]);
            }

        }

        ans.push(p);  //将该点记录在答案的顺序中

    }

    if(ans.size()==n) return 1;  //若答案中的点的数量和n相同，说明可以进行拓扑排序
    else return 0;

}

int main(){

    memset(h,-1,sizeof h);

    cin>>n>>m;

    for(int i=0;i<m;i++){

        int a,b;
        cin>>a>>b;
        add(a,b);
        cnt[b]++;
    }

    if(bfs()){
        while(!ans.empty()){
            cout<<ans.front()<<' ';
            ans.pop();
        }
        cout<<endl;
    }
    else cout<<-1<<endl;

    return 0;

}

3.5 最短路

3.5.1 Dijkstra

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法（单源最短路）

思想

从起始点开始采用贪心策略
每一次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止

注意：Dijkstra不能用于存在负权边的情况

示例：

1. 朴素版本（邻接矩阵）

注意

当建立的图为稠密图时，用邻接矩阵来建图

模板题 849. 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。

输入样例：

输出样例：

代码

#include <bits/stdc++.h>
using namespace std;

const int N=510;

int n,m;

int g[N][N];  //初始化邻接矩阵

int dist[N];  //记录最短路径

bool vis[N];  //标记是否已经确定最短路径

int dijkstra(){

    memset(dist,0x3f,sizeof dist);  //将所有的节点到1号点的初始距离设为INF

    dist[1]=0;  //1到1的距离为0

    for(int i=1;i<=n;i++){

        int t=0;

        for(int j=1;j<=n;j++){

            if(!vis[j]&&dist[j]<dist[t]) t=j;  //遍历vis，找到剩余未确定最短路径的点中距离1最近的点

        }

        for(int j=1;j<=n;j++){

            dist[j]=min(dist[j],dist[t]+g[t][j]);  //更新1到j的点的距离min(dist[j],dist[t]+t到j的边权)（松弛操作）

        }

        vis[t]=1;  //标记已确定t的最短路径

    }

    if(dist[n]==0x3f3f3f3f) return -1;  //若dist[n]距离1为INF，说明走不到n
    else return dist[n];

}

int main(){

    memset(g,0x3f,sizeof g);  //初始化所有的边权为INF

    cin>>n>>m;

    for(int i=0;i<m;i++){

        int a,b,c;

        cin>>a>>b>>c;

        g[a][b]=min(g[a][b],c);  //将重边的边权更新为最小的那一条

    }

    cout<<dijkstra()<<endl;

    return 0;

}

2. 堆优化版本（邻接表）

注意

当建立的图为稀疏图时，用邻接表来建图

优化方式

利用priority_queue优化遍历vis找到未确定的最短路径的点中的距离1最近的点的操作

模板题 850. Dijkstra求最短路 II

原题链接

描述

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

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

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

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

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

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

数据范围 1≤n,m≤1.5×105, 图中涉及边长均不小于 0，且不超过 10000。数据保证：如果最短路存在，则最短路的长度不超过 109。

输入样例：

输出样例：

代码

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;

const int N=1e6+3;

int n,m;

int h[N],e[N],ne[N],w[N],idx;  //初始化邻接表

void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;  //加边操作
}

int dist[N];  //记录最短路径

bool vis[N];  //标记是否已经确定最短路径

int dijkstra(){

    memset(dist,0x3f,sizeof dist);  //将所有的节点到1号点的初始距离设为INF

    dist[1]=0;  //1到1的距离为0

    priority_queue<PII,vector<PII>,greater<PII>> st;  //定义小根堆

    st.push({0,1});  //将起始点的信息入队

    while(!st.empty()){

        auto p=st.top().second;
        st.pop();

        if(vis[p]) continue;  //已确定最短路径的点跳过

        for(int i=h[p];i!=-1;i=ne[i]){  //更新相邻的点的最短距离

            if(dist[e[i]]>dist[p]+w[i]){  //松弛操作

                dist[e[i]]=dist[p]+w[i];
                st.push({dist[e[i]],e[i]});

            }

        }

        vis[p]=1;  //标记已找到最短路径

    }

    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];

}

int main(){

    memset(h,-1,sizeof h);  //初始化邻接表的表头

    cin>>n>>m;

    for(int i=0;i<m;i++){

        int a,b,c;

        cin>>a>>b>>c;

        add(a,b,c);

    }

    cout<<dijkstra()<<endl;

    return 0;

}

3.5.2 Bellman-Ford

思想

初始化所有点到源点的距离为INF,把源点到自己的距离设置为0
遍历n次;每次遍历m条边，用每一条边去更新各点到源点的距离

注意

需要把dist数组进行一个备份，防止每次更新的时候出现串联
由于存在负权边，因此return 0的条件就要改成dist[n]>0x3f3f3f3f/2
Bellman_ford算法可以存在负权回路，因为它求得的最短路限制了边数

模板例题 853. 有边数限制的最短路

原题链接

描述

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

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

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

输入格式

第一行包含三个整数 n,m,k

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

输出格式

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

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

数据范围

1≤n,k≤500 1≤m≤10000 任意边长的绝对值不超过 10000

输入样例：

输出样例：

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+3;

int n,m,k;

int dist[N];  //记录最短路径

int last[N];  //备份dist

struct point{
    int a,b,c;  //存储边的信息
}p[N];

bool b_f(){

    memset(dist,0x3f,sizeof dist);  //将所有的节点到1号点的初始距离设为INF

    dist[1]=0;  //1到1的距离为0

    while(k--){  //限制k次

        memcpy(last,dist,sizeof dist);  //备份dist

        for(int i=0;i<m;i++){

            auto t=p[i];
            dist[t.b]=min(dist[t.b],last[t.a]+t.c);  //松弛操作

        }

    }

    if(dist[n]>0x3f3f3f3f/2) return 0;
    else return 1;

}

int main(){

    cin>>n>>m>>k;

    for(int i=0;i<m;i++){

        int a,b,c;
        cin>>a>>b>>c;

        p[i]={a,b,c};

    }

    if(!b_f()) cout<<"impossible"<<endl;
    else cout<<dist[n]<<endl;

    return 0;

}

3.5.3 SPFA

思想

使用队列优化Bellman-Ford遍历m条边的过程
队列存储每次更新了的点，每条边最多遍历一次
队头不断出队，计算始点起点经过队头到其他点的距离是否变短，如果变短且被点不在队列中，则把该点加入到队尾
重复上述过程，如果存在负权回路，从起点1出发，回到1距离会变小,可以处理负权边和判断负环（抽屉原理）

模板例题

原题链接

描述

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

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

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

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

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

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

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

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

输入样例：

输出样例：

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+3;

int n,m;

int dist[N];  //记录最短路径

bool vis[N];  ////标该点是不是在队列中

int h[N],e[N],ne[N],w[N],idx;  //初始化邻接表

void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;  //加边操作
}

bool spfa(){

    memset(dist,0x3f,sizeof dist);  //将所有的节点到1号点的初始距离设为INF

    dist[1]=0;  //1到1的距离为0

    queue<int> st;  //定义队列

    st.push(1);  //将起始点的信息入队

    while(!st.empty()){

        auto p=st.front();
        st.pop();

        vis[p]=0;  //标记为出队

        for(int i=h[p];i!=-1;i=ne[i]){  //遍历相邻的节点

            if(dist[e[i]]>dist[p]+w[i]){

                dist[e[i]]=dist[p]+w[i];  //松弛操作

                if(!vis[e[i]]){  //若该点不在队列中

                    vis[e[i]]=1;
                    st.push(e[i]);  //入队

                }

            }

        }

    }

    if(dist[n]==0x3f3f3f3f) return 0;
    else return 1;

}

int main(){

    memset(h,-1,sizeof h);

    cin>>n>>m;

    for(int i=0;i<m;i++){

        int a,b,c;

        cin>>a>>b>>c;

        add(a,b,c);

    }

    if(!spfa()) cout<<"impossible"<<endl;
    else cout<<dist[n]<<endl;

    return 0;

}

例题 852. spfa判断负环

原题链接

描述

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

请你判断图中是否存在负权回路。

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

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

输出格式 如果图中存在负权回路，则输出 Yes，否则输出 No。

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

输入样例：

输出样例：

Yes

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+3;

int n,m;

int dist[N];  //记录最短路径

int cnt[N];  //记录入队的次数

bool vis[N];  ////标该点是不是在队列中

int h[N],e[N],ne[N],w[N],idx;  //初始化邻接表

void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;  //加边操作
}

bool spfa(){

    memset(dist,0x3f,sizeof dist);  //将所有的节点到1号点的初始距离设为INF

    dist[1]=0;  //1到1的距离为0

    queue<int> st;  //定义队列

    //点1可能到不了有负环的点， 因此把所有点都加入队列
    for(int i=1;i<=n;i++){
        st.push(i);
        vis[i]=1;
    }

    while(!st.empty()){

        auto p=st.front();
        st.pop();

        vis[p]=0;

        for(int i=h[p];i!=-1;i=ne[i]){  

            if(dist[e[i]]>dist[p]+w[i]){  

                cnt[e[i]]=cnt[p]+1;

                if(cnt[e[i]]>=n) return 0;  //入队大于等于n次说明存在负环

                dist[e[i]]=dist[p]+w[i];

                if(!vis[e[i]]){

                    vis[e[i]]=1;
                    st.push(e[i]);

                }

            }

        }

    }

    return 1;

}

int main(){

    memset(h,-1,sizeof h);

    cin>>n>>m;

    for(int i=0;i<m;i++){

        int a,b,c;

        cin>>a>>b>>c;

        add(a,b,c);

    }

    if(!spfa()) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;

}

3.5.4 Floyd

思想

f[k,i,j]表示从i走到j的路径上除i和j点外只经过1到k的点的所有路径的最短距离。那么f[k,i,j] = min(f[k-1,i,j] , f[k-1,i,k] + f[k-1,k,j])，因此在计算第k层的f[i, j]的时候必须先将第k - 1层的所有状态计算出来，所以需要把k放在最外层
读入邻接矩阵，将次通过动态规划转换为从i到j的最短距离矩阵
判断从a到b是否是无穷大距离时，需要进行if(t > INF/2)判断，而并非是if(t == INF)判断，原因是INF是一个确定的值，并非真正的无穷大，会随着其他数值而受到影响，t大于某个与INF相同数量级的数即可

注意：Floyd 用于求多源汇最短路，时间复杂度为O(n^3)

模板例题 854. Floyd求最短路

原题链接

描述

给定一个 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≤n2 1≤m≤20000, 图中涉及边长绝对值均不超过 10000。

输出样例：

impossible
1

代码

#include <bits/stdc++.h>
using namespace std;

const int N=510;

int dist[N][N];  //记录答案

int n,m,k;

void floyd(){

    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);  //更新最短路径
            }
        }
    }

}

int main(){

    cin>>n>>m>>k;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j) dist[i][j]=0x3f3f3f3f;
        }
    }

    for(int i=0;i<m;i++){

        int a,b,c;

        cin>>a>>b>>c;

        dist[a][b]=min(dist[a][b],c);

    }

    floyd();

    while(k--){

        int a,b;

        cin>>a>>b;

        if(dist[a][b]>0x3f3f3f3f/2) cout<<"impossible"<<endl;
        else cout<<dist[a][b]<<endl;

    }

    return 0;

}

3.6 最小生成树

概念

最小生成树（minimum spanning tree）是由n个顶点，n-1条边，将一个连通图连接起来，且使权值最小的结构
最小生成树可以用Prim算法或Kruskal算法求出

3.6.1 Prim

思想

类似于Dijkstra采用贪心策略
维护一个集合，每次更新集合外的点到集合中任意点的最短距离
将该点加入集合，重复操作，直到所有的点都在集合当中

朴素Prim算法适用于稠密图的情况，稀疏图可以使用堆进行优化，方法同Dijkstra的优化

模板例题 858. Prim算法求最小生成树

原题链接

描述

给定一个 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。

输入样例：

输出样例：

代码

#include <bits/stdc++.h>
using namespace std;

const int N=510;

int n,m;

int g[N][N];  //稠密图使用邻接矩阵存储

int dist[N];  //到集合的最短距离

bool vis[N];  //维护的当前生成树中的点的集合

int res;  //最小生成树边的总长

int prim(){

    memset(dist,0x3f,sizeof dist);  //初始化距离为0x3f3f3f3f

    for(int i=0;i<n;i++){

        int t=-1;

        for(int j=1;j<=n;j++){

            if(!vis[j]&&(t==-1||dist[t]>dist[j])) t=j;  //遍历vis，找到集合外距离集合最近的点

        }

        if(i&&dist[t]==0x3f3f3f3f) return dist[t];  //若距离集合为INF说明没有最小生成树
        if(i) res+=dist[t];

        for(int j=1;j<=n;j++){

            dist[j]=min(dist[j],g[t][j]);  //更新其他点到集合的最短距离

        }

        vis[t]=1;  //标记为存在集合中

    }

    return res;

}

int main(){

    cin>>n>>m;

    memset(g,0x3f,sizeof g);

    for(int i=0;i<m;i++){

        int a,b,c;

        cin>>a>>b>>c;

        g[a][b]=g[b][a]=min(g[a][b],c);  //建立无向图，重边取最小

    }

    int p=prim();

    if(p==0x3f3f3f3f) cout<<"impossible"<<endl;
    else cout<<p<<endl;

    return 0;

}

3.6.2 Kruskal

思想

先对所有的边按照边权从小到大进行排序
遍历排序后的所有边，用并查集来维护最小生成树的集合
若两个点不在同一集合中，则合并两个集合
重复操作，直到所有的连通块合并，最终的集合为最小生成树的集合

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

原题链接

描述

给定一个 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≤105, 1≤m≤2∗105, 图中涉及边的边权的绝对值均不超过 1000。

输入样例：

输出样例：

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+3;

int n,m;

int p[N];  //并查集来维护连通块

int ans,cnt;  //ans为当前生成树的总边权，cnt为当前生成树边的数量

struct point{  //记录边的信息
    int x,y,z;

    bool operator<(const point &p)const{  //重载小于号
        return z<p.z;
    }

}g[N];

int find(int x){  //并查集查询操作

    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];

}

int kruskal(){

    sort(g,g+m);  //先对边权进行排序

    for(int i=1;i<=n;i++) p[i]=i;  //初始化并查集

    for(int i=0;i<m;i++){  //枚举m条边

        int a=g[i].x,b=g[i].y,c=g[i].z;

        a=find(a),b=find(b);

        if(a!=b){  //如果a和b不在同一个集合中

            p[a]=b;  //合并a和b
            ans+=c;  //更新总边权
            cnt++;  //总边数加一

        }

    }

    if(cnt!=n-1) return 0x3f3f3f3f;  //总边数!=n-1说明没有最小生成树
    else return ans;

}

int main(){

    cin>>n>>m;

    for(int i=0;i<m;i++){

        int a,b,c;

        cin>>a>>b>>c;

        g[i]={a,b,c};

    }

    if(kruskal()==0x3f3f3f3f) cout<<"impossible"<<endl;
    else cout<<ans<<endl;

    return 0;

}

3.7 二分图

概念

将图的点分配到两个集合中，使得图的每一条边相连的两个点不在同一集合中
即图中的点可以分成左右两部分，左侧的点只和右侧的点相连，右侧的点只和左侧的点相连

注意：若改图存在奇数环（构成环的点有奇数个）则无法生成二分图

示例：

3.7.1 染色法判断二分图

思想

首先在图中选择任意一点开始染色
判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色
若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断
可以使用DFS或BFS实现

模板例题 860. 染色法判定二分图

原题链接

描述

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。

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

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

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

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

数据范围 1≤n,m≤105 输入样例：

输出样例：

Yes

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+3;

int n,m;

int h[N],e[N],ne[N],idx;  //初始化邻接表

int vis[N];  //标记染的颜色

void add(int a,int b){

    e[idx]=b,ne[idx]=h[a],h[a]=idx++;  //加边操作

}

int flag=1;  //标记是否可以生成二分图

bool dfs(int u,int c){

    vis[u]=c;  //将该点染色

    for(int i=h[u];i!=-1;i=ne[i]){  //遍历该点的相邻点

        if(!vis[e[i]]){  //若该点未染色

            if(!dfs(e[i],3-c)) return 0;  //染色为2，若递归染色结果为false说明无法生成二分图

        }
        else if(vis[e[i]]==c) return 0;  //若该点已经染色，判断该点颜色是否相同，相同说明无法生成二分图

    }

    return 1;

}

int main(){

    memset(h,-1,sizeof h);  

    cin>>n>>m;

    for(int i=0;i<m;i++){

        int a,b;

        cin>>a>>b;

        add(a,b),add(b,a);  //建立无向图

    }

    for(int i=1;i<=n;i++){

        if(!vis[i]){  //若该点未染色

            if(!dfs(i,1)){  //若染色为1

                flag=0;  //若递归染色结果为false，标记为无法生成二分图
                break;

            }

        }

    }

    if(flag) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;

}

3.7.2 匈牙利算法

概念

匹配：在二分图中，任意两条边都没有公共顶点（一对一）的一组边称为一组匹配
最大匹配：一个图所有匹配中，所含匹配的边数最多的匹配，称为这个图的最大匹

思想

基于Hall定理中充分性证明的思想
核心是寻找增广路径，用增广路径求二分图最大匹配

模板例题 861. 二分图的最大匹配

原题链接

描述

给定一个二分图，其中左半部包含 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 输入样例：

输出样例：

代码

#include <bits/stdc++.h>
using namespace std;

int n1,n2,m;

int res;

const int N=1e6+3;

int match[N];  //记录当前配对的信息

bool vis[N];  //标记当前匹配阶段是否发生过配对

int h[N],e[N],ne[N],idx;  //初始化邻接表，存稀疏图

void add(int a,int b){

    e[idx]=b,ne[idx]=h[a],h[a]=idx++;  //加边操作

}

bool find(int u){  //判断是否可以配对

    for(int i=h[u];i!=-1;i=ne[i]){  //遍历该点的所有相邻点

        if(!vis[e[i]]){  //若在该次模拟中,该点尚未被匹配

            vis[e[i]]=1;  //标记为匹配

            if(match[e[i]]==0||find(match[e[i]])){  //若该点最终没有配对，或原来的配对的点可以找到其他新的配对

                match[e[i]]=u;  //更新匹配的状态
                return 1;  //匹配成功

            }

        }

    }

    return 0;

}

int main(){

    memset(h,-1,sizeof h);

    cin>>n1>>n2>>m;

    for(int i=0;i<m;i++){

        int a,b;

        cin>>a>>b;

        add(a,b);

    }

    for(int i=1;i<=n1;i++){

        memset(vis,0,sizeof vis);  //每次模拟匹配，需要初始化
        if(find(i)) res++;

    }

    cout<<res<<endl;

}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-6-25 1，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法