【AcWing算法基础课】第三章 搜索与图论

文章目录

前言

本专栏文章为本人AcWing算法基础课的学习笔记，课程地址在这。如有侵权，立即删除。

课前温习

一、深度优先搜索（DFS）

特点：尽可能先向纵深方向搜索。使用

stack

实现。所需空间**O(h)**（h为深度）。不具有“最短性”。

1、排列数字

题目链接：842. 排列数字

1.1题目描述

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。现在，请你按照 字典序 将所有的排列方法输出。

输入格式

共一行，包含一个整数 n 。

输出格式

按字典序输出所有排列方案，每个方案占一行。

数据范围

1≤n≤7

输入样例：

3

输出样例：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

1.2思路分析

1. dfs 注意 顺序，为树形结构遍历，形式如图。

2.回溯时，需 恢复现场。

1.3代码实现

#include<iostream>usingnamespace std;constint N =10;int n;int path[N];//记录每种方案bool st[N];//记录数字是否被用过 voiddfs(int u){//当添到最后一个数时，到达最后一层，最后一个数已确定，直接输出 if(u==n){for(int i=0;i<n;i++){
            cout<<path[i]<<" ";}
        cout<<endl;return;}//如果没填完时for(int i=1;i<=n;i++){//如果当前数没被用过 if(!st[i]){
            path[u]=i;//把数字填到当前位置 
            st[i]=true;//记录数字已被用过 dfs(u+1);//处理完后走到下一层 
            st[i]=false;//恢复现场 }}}intmain(){  cin>>n;dfs(0);return0;}

2、 n-皇后问题

题目链接：843. n-皇后问题

1.4题目描述

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

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

输入格式

共一行，包含整数 n。

输出格式

每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后，输出一个空行。
注意：行末不能有多余空格。
输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围

1≤n≤9

输入样例：

4

输出样例：

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

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

1.5思路分析

思路1：按照上题思路，（枚举每一行的皇后应该放到哪个位置（每行一个皇后））然后进行减枝。
（每条对角线）

思路2：
枚举每个格子是否放皇后,每次都有两种选择，放或者不放，当到枚举到第n行第n列结束。

1.6代码实现

思路1代码：

#include<iostream>usingnamespace std;constint N =20;int n;char g[N][N];//记录方案 bool col[N],dg[N],udg[N];//记录列、正对角线、反对角线是否出现过 voiddfs(int u){//找到一种方案输出 if(u==n){for(int i=0;i<n;i++){
            cout<<g[i]<<endl;}
        cout<<endl;return;}//枚举每一列，看皇后可放在哪一列for(int i=0;i<n;i++){//如果列、正对角线、副对角线没有出现过 //对角利用一次函数截距，y=-x+b,则b=y+x;y=x+b,则b=y-x,（本题可视为x为行下标，y为列下标，第一行为x轴，第一列为y轴，而每两条匹配的正副对角线，与y轴截距相同，可以据此来已有一条对角线的前提下，找出它的正/副对角线）因下标不为负数，此情况需要将每个副对角线加一个正数保证下标为正，正数随便加，但也不能使数组下标越界。if(!col[i]&&!dg[u+i]&&!udg[n-u+i]){
            g[u][i]='Q';  
            col[i]=dg[u+i]=udg[n-u+i]=true;dfs(u+1);  
            col[i]=dg[u+i]=udg[n-u+i]=false; 
            g[u][i]='.';}}}intmain(){  cin>>n;for(int i=0;i<n;i++){for(int j=0;j<n;j++){
           g[i][j]='.';}}dfs(0);return0;}

思路2代码：

#include<iostream>usingnamespace std;constint N =20;int n;char g[N][N];//记录方案 bool row[N],col[N],dg[N],udg[N];//记录行、列、正对角线、反对角线是否出现过 voiddfs(int x,int y,int s){//x,y代表格子坐标，s代表皇后个数 //如果已出界，则将格子转到下一行第一个 if(y==n){
       y=0;
       x++;}if(x==n){//如果皇后数量为n，则是一种方案，输出 if(s==n){for(int i=0;i<n;i++){
                cout<<g[i]<<endl;}
            cout<<endl;}return;//注意return位置，当x越界，无论是否是一种方案，均返回，结束搜索}//不放皇后 dfs(x,y+1,s);//放皇后 if(!row[x]&&!col[y]&&!dg[x+y]&&!udg[x-y+n]){
            g[x][y]='Q';  
            row[x]=col[y]=dg[x+y]=udg[x-y+n]=true;dfs(x,y+1,s+1);  
            row[x]=col[y]=dg[x+y]=udg[x-y+n]=false; 
            g[x][y]='.';}}intmain(){  cin>>n;for(int i=0;i<n;i++){for(int j=0;j<n;j++){
           g[i][j]='.';}}dfs(0,0,0);return0;}

二、宽度优先搜索（BFS）

特点：尽可能先进行横向搜索。使用

queue

实现。所需空间**O(2h)**（h为深度）。具有“最短性”(边权都为1时，可以用BFS求最短路)。

1、走迷宫

题目链接：844. 走迷宫

2.1题目描述

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

输入样例：

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出样例：

8

2.2思路分析

利用宽搜进行模拟，具体看代码注释部分。
(若要输出路径只需要记录每个点的前一个点，即在入队之前将该点记录下来，如下y总代码，Prev数组便是来记录点是由哪个点转移来)

2.3代码实现

#include<iostream>#include<string.h>#include<queue>usingnamespace std;typedef pair<int,int> PII;constint N=110;int n,m;int g[N][N];//存储迷宫地图 int d[N][N];//每个点到起点的距离
queue<PII> q;intbfs(){
    q.push({0,0});memset(d,-1,sizeof d);//初始化距离均为-1，代表每个点没有被走过 (代替了标记数组)
    d[0][0]=0;//利用方向数组模拟上下左右四个点 int dx[]={-1,0,1,0};int dy[]={0,1,0,-1};while(!q.empty()){
        PII temp=q.front();
        q.pop();for(int i=0;i<4;i++){int x=temp.first+dx[i],y=temp.second+dy[i];//每次循环x,y代表周围的点 //如果点在界内且该点可走且该点没有被走过，将这个点计入路径 if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1){
               d[x][y]=d[temp.first][temp.second]+1;
               q.push({x,y});}}}return d[n-1][m-1];}intmain(){  cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){
           cin>>g[i][j];}}
   cout<<bfs()<<endl;return0;}

三、树与图的存储

• 树是一种特殊的图，与图的存储方式相同。
• 对于无向图中的边ab，存储两条有向边a->b, b->a。 因此我们可以只考虑有向图的存储。
• 两种存储方式：(1）邻接矩阵：g[a][b] 存储边a->b(2）邻接表//对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点。int h[N],e[M],ne[M],idx;/*idx代表边的下标索引（编号） h[N]存储N个链表的头结点（第一条边的idx） e[M]存储第idx条边终点的值 ne[M]存储第idx条边 同起点的下一条边的编号（idx） idx表示当前边的编号*///添加一条边a->bvoidadd(int a,int b){ e[idx]=b; ne[idx]=h[a]; h[a]=idx++;}//初始化idx=0;memset(h,-1,sizeof h);

四、树与图的遍历

1、深度优先遍历（846. 树的重心）

核心模板

时间复杂度：O(n+m),n表示点数，m表示边数。

intdfs(int u){
    st[u]=true;//stu[u]表示点u已经被遍历过for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(!st[j])dfs(j);}}

题目链接：846. 树的重心

4.1题目描述

给定一颗树，树中包含 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

4.2思路分析

• 依次对于每个点，并分别求出删除该点后各个连通块中点数的最大值，然后针对求出来的每个最大值，再取最小值，即为答案。
• 通过深度优先遍历求每个子树中点的个数，而子树的子树可以递归求解，对于子树的上面部分的连通块中点的个数直接用总数减去子树的点数即可。

4.3代码实现

#include<iostream>#include<string.h>usingnamespace std;constint N=100010,M=N*2;//N代表点，M代表边 int h[N],e[M],ne[M],idx;int n;bool st[N];//标记点是否处理/出现过 int ans=N;//记录答案 /*
  idx表示边的编号 
  h数组存储每个结点的第一条边的idx 
  e数组存储第idx条边的终点
  ne数组存储以第idx条边的起点为起点的第idx条边的下一条边 
*/voidadd(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;}//以u为根的子树中点的数量 intdfs(int u){
    st[u]=true;//标记u已经被搜过 int sum=1,res=0;//sum代表当前子树的大小(结点个数)，res代表删除点以后连通块中点数的最大值for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(!st[j]){int s=dfs(j);//s代表当前子树的大小
            res=max(res,s);//当前子树中点的数量也要在总连通块中点的数量取max
            sum+=s;//当前子树是以u为根结点子树的一部分，以u结点为根子树中结点的数量要加上这部分 }}
    res=max(n-sum,res);//n-sum代表除以u为根结点的子树外，剩余部分（上部分）所组成连通块中点的数量 
    ans=min(ans,res);//答案是连通块中点的数量最大值中的最小值 return sum;}intmain(){  cin>>n;memset(h,-1,sizeof h);for(int i=0;i<n-1;i++){int a,b;
       cin>>a>>b;add(a,b),add(b,a);//无向边需添加两条边 }dfs(1);
   cout<<ans<<endl;return0;}

2、宽度优先遍历（847. 图中点的层次）

时间复杂度：O(n+m),n表示点数，m表示边数。

核心模板

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

题目链接：847. 图中点的层次

4.4题目描述

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

4.5思路分析

• 基本框架

4.6代码实现

可手写队列，也可直接使用stl内置队列。
使用STL内置队列代码

#include<iostream>#include<string.h>#include<queue>usingnamespace std;constint N=100010;int h[N],e[N],ne[N],idx;int n,m;int d[N];
queue<int> q;voidadd(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;}intbfs(){
    q.push(1);memset(d,-1,sizeof d);
    d[1]=0;while(!q.empty()){int t=q.front();
        q.pop();for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(d[j]==-1){
                q.push(j);
                d[j]=d[t]+1;}}}return d[n];}intmain(){int a,b;memset(h,-1,sizeof h);
    cin>>n>>m;for(int i=0;i<m;i++){
        cin>>a>>b;add(a,b);}
    cout<<bfs();return0;}

手写模拟队列代码

#include<iostream>#include<string.h>usingnamespace std;constint N=100010;int h[N],e[N],ne[N],idx;int n,m;int d[N],q[N];//d[]代表距离，q[]模拟队列 /*
  idx表示边的编号 
  h数组存储每个结点的第一条边的idx 
  e数组存储第idx条边的终点
  ne数组存储以第idx条边的起点为起点的第idx条边的下一条边 
*/voidadd(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;}intbfs(){int hh=0,tt=0;//定义队头和队尾
    q[0]=1;memset(d,-1,sizeof d);//初始化都为-1代表都没被遍历过（代替了标记数组）
    d[1]=0;while(hh<=tt){int t=q[hh++];//t每次取队头元素//遍历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;//到达j点的距离为到达t点的距离+1 
                q[++tt]=j;//队尾插入j }}}return d[n];}intmain(){  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;return0;}

五、拓扑排序（848. 有向图的拓扑序列）

有向无环图称为拓扑图，拓扑序列满足：如果存在vi到vj的路径，则顶点vi必然在顶点vj之前。

核心模板

时间复杂度：**O(n+m)**，n表示点数，m表示边数。

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

题目链接：848. 有向图的拓扑序列

5.1题目描述

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

输入样例：

3 3
1 2
2 3
1 3

输出样例：

1 2 3

5.2思路分析

一个有向无环图至少存在一个入度为0的点。

1. 所有入度为0的点都可作为最开始的点，将它们入队。
2. 然后枚举队头的每条出边，并且删掉（因为队头点已在拓扑序列第一个点），来找下一个入度为0的点，然后入队。
3. 如果所有点都入队了，说明存在拓扑序列；否在不存在拓扑序列。队列元素顺序即为拓扑序列。

5.3代码实现

y总手动模拟队列代码

我的代码
注：不能像y总那样直接输出队列即为答案的原因：因为y总的手写队列可以访问队头已出队元素，而

STL

中

queue

不能，所以需要将答案记录下来。

#include<iostream>#include<cstring>#include<queue>usingnamespace std;constint N=100010;int h[N],e[N],ne[N],idx;int n,m;int d[N],ans[N],num;//d[]代表点的入度,ans为结果数组 ,num代表结果数组的长度 
queue<int> q;/*
  idx表示边的编号 
  h数组存储每个结点的第一条边的idx 
  e数组存储第idx条边的终点
  ne数组存储以第idx条边的起点为起点的第idx条边的下一条边 
*/voidadd(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;}booltp(){for(int i=1;i<=n;i++){//如果入度为0，则入队 if(!d[i]){
            q.push(i);}}while(!q.empty()){int t=q.front();//取队头元素
        q.pop();
        ans[num++]=t;//遍历队头元素的每个邻点for(int i=h[t];i!=-1;i=ne[i]){//找到队头元素出边的终点 int j=e[i];//删掉出边
             d[j]--;//如果删完后j入度为0，则也入队 if(d[j]==0){
                 q.push(j);}}}//所有点都入队才存在拓扑序列 return num==n;}intmain(){  cin>>n>>m;memset(h,-1,sizeof h);for(int i=0;i<m;i++){int a,b;
       cin>>a>>b;add(a,b);
       d[b]++;//每多一条指向b的边，b的入度加1 }if(tp()){for(int i=0;i<n;i++){
             cout<<ans[i]<<" ";}}else{
       cout<<-1;}return0;}

六、Dijkstra算法

源点即起点，汇点即终点。

n表示点数，m表示边数

稠密图：m和n2一个级别
稀疏图：m和n一个级别

核心模板

稠密图用邻接矩阵存储，稀疏图用邻接表存储。

1. 朴素dijkstra算法

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

int g[N][N];//存储每条边int dist[N][N];//存储1号点到每个点的最短距离bool st[N];//存储每个点的最短路是否已经确定//求1号点到n号点的最短路，如果不存在则返回-1intdijkstra(){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];}

• 下图来自AcWing官网，作者们如图，侵权删。

1. 堆优化版dijkstra

手写堆可以保证堆中元素个数一定，而优先队列不可以修改任意一个元素，只能继续插入新的点，有冗余。

• 下图来自AcWing官网，作者们如图，侵权删。时间复杂度是O(mlogn)，n表示点数，m表示边数。

typedef pair<int,int> PII;int n;//点的数量int h[N],w[M],e[M],ne[M],idx;//领接表存储所有边int dist[N];//存储所有点到1号点的距离bool st[N];//存储每个点的最短距离是否已确定//求1号点到n号点的最短距离，如果不存在，则返回-1intdijkstra(){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;//distance等同于dist[ver]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});//注意与spfa区分，此时只要更新最短路就入堆}}}if(dist[n]==0x3f3f3f3f)return-1;return dist[n];}

题目一

题目链接：849. Dijkstra求最短路 I

6.1题目描述

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

6.2思路分析

套用模板即可，注意细节

6.3代码实现

#include<iostream>#include<cstring>usingnamespace std;constint N=510;int n,m;int g[N][N];//稠密图用领接矩阵存储，存储两个点之间的距离 int dist[N];//存储从1号点走到每个点的当前最短距离 bool st[N];//存储每个点的最短路是否确定 intdijkstra(){memset(dist,0x3f,sizeof dist);//初始化从1号点走到每个点的距离为正无穷 
    dist[1]=0;//1号点走到自己的最短距离为0 for(int i=0;i<n;i++){int t=-1;//t在还未确定最短路的点中寻找距离最短的点 for(int j=1;j<=n;j++){//在st[]=false的点中找dist[]最小的点//如果当前点没有确定最短路而且t没有更新过或者当前点没有确定最短路而且t已经更新过，但是j离1号点距离更短，则更新t if(!st[j]&&(t==-1||dist[t]>dist[j]))  t=j;}
        st[t]=true;//t已确定最短路//更新最短路，看是否存在从t走到j再走到终点的距离比j直接走到终点距离小，若存在则更新 for(int j=1;j<=n;j++){
            dist[j]=min(dist[j],dist[t]+g[t][j]);}}//如果最短路没有被更新过，说明走不到终点返回-1，否则返回最短路 if(dist[n]==0x3f3f3f3f)return-1;return dist[n];}intmain(){
    cin>>n>>m;//初始化邻接矩阵 memset(g,0x3f,sizeof g);while(m--){int a,b,c;
        cin>>a>>b>>c;//因为存在重边和自环，所以两点间距离取最短的即可 
        g[a][b]=min(g[a][b],c);}int t=dijkstra();
    cout<<t;return0;}

题目二

题目链接：850. Dijkstra求最短路 II

6.4题目描述

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

输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

6.5思路分析

利用堆优化dijkstra算法，套用模板即可，注意细节。

6.6代码实现

#include<iostream>#include<cstring>#include<queue>#include<utility>usingnamespace std;typedef pair<int,int> PII;//两个值分别存储每个点到1号点最短距离和点编号 constint N=150010;int n,m;int h[N],w[N],e[N],ne[N],idx;//邻接表存储每条边,w[]代表每条边的权重 int dist[N];//存储1号点到n号点的最短距离 bool st[N];//存储每个点的最短距离是否已经确定 //邻接表加边 voidadd(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;}intdijkstra(){memset(dist,0x3f,sizeof dist);
    dist[1]=0;//1号点到1号点（自己）的距离为0 
    priority_queue<PII,vector<PII>,greater<PII>> heap;//建立小根堆 
    heap.push({0,1});//将起点放入堆中 while(heap.size()){auto t=heap.top();//t取出当前距离最小的点（即堆顶元素） 
        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]){//如果从1号点到ver点再到j点的距离比从1号点直接到j点的距离小，则更新1号点到j的最短距离为前者 
                dist[j]=distance+w[i];
                heap.push({dist[j],j});//把更新后的的距离和该点编号，入堆 }}}if(dist[n]==0x3f3f3f3f)return-1;//如果无法从1号点到达n号点返回-1 return dist[n];//否则返回从1号点到n号点的距最短离 }intmain(){
    cin>>n>>m;memset(h,-1,sizeof h);while(m--){int a,b,c;
        cin>>a>>b>>c;add(a,b,c);}int t=dijkstra();
    cout<<t;return0;}

七、Bellman-Ford算法

存在最短路则一定不存在负权回路，如果存在负权回路则最短路可能是负无穷。

时间复杂度O(nm)，n表示点数，m表示边数

核心模板

int n,m;//n表示点数，m表示边数int dist[N];//dist[x]存储1到x的最短路距离structEdge{//边，a表示出点，b表示入点，w表示边的权重int a,b,w;}edge[M];//求1到n的最短路距离，如果无法从1走到n，返回-1intbellman_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];}

题目链接：853. 有边数限制的最短路

7.1题目描述

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

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

impossible

。

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

输入格式

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

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

点的编号为 1∼n。

输出格式

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

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

impossible

。

数据范围

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

输入样例：

3 3 1
1 2 1
2 3 1
1 3 3

输出样例：

3

7.2思路分析

套用模板即可，注意细节。

7.3代码实现

#include<iostream>#include<algorithm>#include<cstring>usingnamespace std;constint N=510,M=10010;int n,m,k;int backup[N];//存储上一次循环中dist[]数组的值 int dist[N];//存储1号点到n号点的最短距离 //利用结构体存每条边：a起点，b终点，w权重 structEdge{int a,b,w;}edges[M];intbellman_ford(){memset(dist,0x3f,sizeof dist);
    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;
            dist[b]=min(dist[b],backup[a]+w);}}if(dist[n]>0x3f3f3f3f/2)return-3;//不能写成==，如果图中某个点是无法到达，到达该点的最短距离为0x3f3f3f3f，而这个点到最后一个点的最短距离为-1，则会导致dist[n]！=0x3f3f3f3f,但是这个点不能到达n号点 return dist[n];}intmain(){
    cin>>n>>m>>k;for(int i=0;i<m;i++){int a,b,w;
        cin>>a>>b>>w;
        edges[i]={a,b,w};}int t=bellman_ford();if(t==-3)  cout<<"impossible";else cout<<t;return0;}

八、spfa算法（队列优化的Bellman-Ford算法）

1. 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号点则返回-1intspfa(){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];//注意与dijkstra堆优化区分，此时如果不在队列才入队if(!st[j]){//注意该判断语句的位置（在第一个if中） //如果队列中已存在j，则不需要将j重复插入
                    q.push(j);
                    st[j]=true;}}}}if(dist[n]==0x3f3f3f3f)return-1;return dist[n];}

1. 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，否则返回falseboolspfa(){//不需要初始化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)returntrue;//如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环if(!st[j]){
                    q.push(j);
                    st[j]=true;}}}}returnfalse;}

题目一

题目链接：851. spfa求最短路

8.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。

输入样例：

3 3
1 2 5
2 3 -3
1 3 4

输出样例：

2

8.2思路分析

套用模板即可，注意细节。

8.3代码实现

#include<iostream>#include<cstring>#include<queue>usingnamespace std;constint N=150010;int n,m;int h[N],w[N],e[N],ne[N],idx;//邻接表存储每条边,w[]代表每条边的权重 int dist[N];//存储1号点到n号点的最短距离 bool st[N];//存储每个点是否已经在队列中，防止队列中存储重复的点 //邻接表加边 voidadd(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;}intspfa(){memset(dist,0x3f,sizeof dist);
    dist[1]=0;//1号点到1号点（自己）的距离为0 
    queue<int> q;//队列中存储能被更新的更新后的点（更新后的点，其后的点的距离才会被更新，否则无意义） 
    q.push(1);//将1号点入队 while(q.size()){int 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不在队列中，则加入 
                    q.push(j);
                    st[j]=true;}}}}if(dist[n]==0x3f3f3f3f)return-3;//如果无法从1号点到达n号点返回-1 return dist[n];//否则返回从1号点到n号点的距最短离 }intmain(){
    cin>>n>>m;memset(h,-1,sizeof h);while(m--){int a,b,c;
        cin>>a>>b>>c;add(a,b,c);}int t=spfa();if(t==-3) cout<<"impossible";else cout<<t;return0;}

题目二

题目链接：852. spfa判断负环

8.4题目描述

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

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

输入格式

第一行包含整数 n 和 m。

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

输出格式

如果图中存在负权回路，则输出

Yes

，否则输出

No

。

数据范围

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

输入样例：

3 3
1 2 -1
2 3 4
3 1 -4

输出样例：

Yes

8.5思路分析

套用模板即可，注意细节。

• 下图来自AcWing官网，作者们如图，侵权删。

8.6代码实现

#include<iostream>#include<cstring>#include<queue>usingnamespace std;constint N=150010;int n,m;int h[N],w[N],e[N],ne[N],idx;//邻接表存储每条边,w[]代表每条边的权重 int dist[N],cnt[N];//dist[]存储1号点到n号点的最短距离，cnt[i]存储从1号点到i号点经过的点的数量bool st[N];//存储每个点是否已经在队列中，防止队列中存储重复的点 //邻接表加边 voidadd(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;}intspfa(){
    queue<int> q;//队列中存储能被更新的更新后的点（更新后的点，其后的点的距离才会被更新，否则无意义） //将所有点入队for(int i=1;i<=n;i++){
        st[i]=true;   
        q.push(i);}while(q.size()){int 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;//j经过的点数加1if(cnt[j]>=n)returntrue;if(!st[j]){//如果j不在队列中，则加入 
                    q.push(j);
                    st[j]=true;}}}}returnfalse;}intmain(){
    cin>>n>>m;memset(h,-1,sizeof h);while(m--){int a,b,c;
        cin>>a>>b>>c;add(a,b,c);}if(spfa()) cout<<"Yes";else cout<<"No";return0;}

九、floyd算法

核心模板

• 下图来自AcWing官网，作者们如图，侵权删。时间复杂度是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的最短距离voidfloyd(){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]);}}}}

题目链接：854. Floyd求最短路

9.1题目描述

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

输入样例：

3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3

输出样例：

impossible
1

9.2思路分析

套用模板即可，注意细节。

9.3代码实现

#include<iostream>#include<algorithm>usingnamespace std;constint N=210,INF=1e9;int n,m,q;int d[N][N];//邻接矩阵voidfloyd(){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]);}}}}intmain(){
    cin>>n>>m>>q;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;}}while(m--){int a,b,w;
        cin>>a>>b>>w;
        d[a][b]=min(d[a][b],w);//如果有重边只取最短的}floyd();while(q--){int a,b;
        cin>>a>>b;if(d[a][b]>INF/2) cout<<"impossible"<<endl;else cout<<d[a][b]<<endl;}return0;}

十、Prim算法

核心模板

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

int n;//n表示点数int g[N][N];//邻接矩阵，存储所有边int dist[N];//存储其他点到当前最小生成树的距离bool st[N];//存储每个点是否已经在生成树中//如果图不连通，则返回INF（值是0x3f3f3f3f），否则返回最小生成树的树边权重之和intprim(){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;}

题目链接：858. Prim算法求最小生成树

10.1题目描述

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

10.2思路分析

套用模板即可，注意理解算法思想，注意细节。

10.3代码实现

#include<iostream>#include<algorithm>#include<cstring>usingnamespace std;constint N=510,INF=0x3f3f3f3f;int n,m;int g[N][N];//邻接矩阵存储所有边int dist[N];//存储其他点到当前最小生成树的距离bool st[N];//存储每个点是否已经在生成树中intprim(){memset(dist,0x3f,sizeof dist);//初始化所有点距离当前最小生成树的距离为正无穷int res=0;//res存储最小生成树边的权重之和for(int i=0;i<n;i++){//循环n次，每次去找当前距离最小生成树的距离最小的点，记录在t中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;//如果距离最小仍然是正无穷，说明图并不连通，返回INFif(i) res+=dist[t];//将距离累加进答案中for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);//以当前距离最小的点来更新其他点
        st[t]=true;//标记为已在生成树中}return res;}intmain(){
    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();if(t==INF) cout<<"impossible"<<endl;else cout<<t<<endl;return0;}

十一、Flood Fill算法

既可以宽搜实现，也可以深搜实现，宽搜具有最短性，深搜方便写，但容易爆栈。

宽搜思路：每次将周围的点放入队列，然后一圈一圈地往外扩展。

深搜思路：每次按四个方向分别进行扩展，直到一个方向无法进行扩展时，回溯。

题目链接：1113. 红与黑

11.1题目描述

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。

你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。

请写一个程序，计算你 总共能够到达多少块黑色的瓷砖。

输入格式

输入包括多个数据集合。

每个数据集合的第一行是两个整数 W 和 H，分别表示 x 方向和 y 方向瓷砖的数量。

在接下来的 H 行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下

1）‘.’：黑色的瓷砖；

2）‘#’：红色的瓷砖；

3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

当在一行中读入的是两个零时，表示输入结束。

输出格式

对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

数据范围

1≤W,H≤20

输入样例：

6 9 
....#. 
.....# 
...... 
...... 
...... 
...... 
...... 
#@...# 
.#..#. 
0 0

输出样例：

45

11.2思路分析

利用Flood Fill算法，注意细节。

11.3代码实现

bfs代码

#include<iostream>#include<queue>#include<utility>usingnamespace std;typedef pair<int,int> PII;constint N=25;int w,h;int dx[]={1,-1,0,0},dy[]={0,0,1,-1};//方向数组char g[N][N];int ans;intbfs(int x,int y){
    queue<PII> q;
    q.push({x,y});       
    g[x][y]='#';//修改当前格子内容，表示已遍历过int res=0;while(!q.empty()){
        PII t=q.front();
        q.pop();
        res++;//拓展队头for(int i=0;i<4;i++){int a=t.first+dx[i],b=t.second+dy[i];if(a>=0&&a<h&&b>=0&&b<w&&g[a][b]=='.'){
                res+=bfs(a,b);}}}return res;}intmain(){while(cin>>w>>h,w||h){for(int i=0;i<h;i++){for(int j=0;j<w;j++){
                cin>>g[i][j];}}for(int i=0;i<h;i++){for(int j=0;j<w;j++){if(g[i][j]=='@') ans=bfs(i,j);}}
        cout<<ans<<endl;}return0;}

y总代码

#include<iostream>#include<queue>#include<utility>usingnamespace std;typedef pair<int,int> PII;constint N=25;int dx[]={1,-1,0,0},dy[]={0,0,1,-1};char g[N][N];int w,h;int ans;intbfs(int x,int y){
    queue<PII> q;
    q.push({x,y});
    g[x][y]='#';int res=0;while(!q.empty()){
        PII t=q.front();
        q.pop();
        res++;for(int i=0;i<4;i++){int a=t.first+dx[i],b=t.second+dy[i];if(a>=0&&a<h&&b>=0&&b<w&&g[a][b]=='.'){
                g[a][b]='#';
                q.push({a,b});}}}return res;}intmain(){while(cin>>w>>h,w||h){//while循环条件为w||h的值for(int i=0;i<h;i++){for(int j=0;j<w;j++){
                cin>>g[i][j];}}for(int i=0;i<h;i++){for(int j=0;j<w;j++){if(g[i][j]=='@') ans=bfs(i,j);}}
        cout<<ans<<endl;}return0;}

dfs代码

#include<iostream>usingnamespace std;constint N=25;int w,h;int dx[]={1,-1,0,0},dy[]={0,0,1,-1};//方向数组char g[N][N];int ans;intdfs(int x,int y){int res=1;
    g[x][y]='#';//修改当前位置的值，表示已经遍历过//递归扩展四个方向for(int i=0;i<4;i++){int a=x+dx[i],b=y+dy[i];if(a>=0&&a<h&&b>=0&&b<w&&g[a][b]=='.'){
            res+=dfs(a,b);}}return res;}intmain(){while(cin>>w>>h,w||h){for(int i=0;i<h;i++){for(int j=0;j<w;j++){
                cin>>g[i][j];}}for(int i=0;i<h;i++){for(int j=0;j<w;j++){if(g[i][j]=='@') ans=dfs(i,j);}}
        cout<<ans<<endl;}return0;}

十二、Kruskal算法

时间复杂度是O(mlogn)，n表示点数，m表示边数

核心模板

模板1

int n,m;//n是点数，m是边数int p[N];//并查集的父结点数组//存储边structEdge{int a,b,w;booloperator<(const Edge &w)const{return w<W.w;}}edges[M];//并查集核心操作intfind(int x){if(p[x]!=x) p[x]=find(p[x]);return p[x];}intkruskal(){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;}

模板2

int n,m;//n是点数，m是边数int p[N];//并查集的父结点数组//存储边structEdge{int a,b,w;}edges[M];//手写比较函数，使sort能够为结构体排序boolcmp(Edge A,Edge B){return A.w<B.w;}//并查集核心操作intfind(int x){if(p[x]!=x) p[x]=find(p[x]);return p[x];}intkruskal(){sort(edges,edges+m,cmp);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;}

题目链接：859. Kruskal算法求最小生成树

12.1题目描述

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

输入样例：

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

输出样例：

6

12.2思路分析

利用Kruskal算法，注意细节，具体思想见注释部分。

12.3代码实现

代码1

#include<iostream>#include<algorithm>usingnamespace std;constint N=200010;int n,m;int p[N];//并查集祖宗结点数组//结构体存储每条边structEdge{int a,b,w;//重载小于号booloperator<(const Edge &W)const{return w<W.w;}}edges[N];//并查集查找组总结点操作intfind(int x){if(p[x]!=x) p[x]=find(p[x]);return p[x];}intmain(){
    cin>>n>>m;for(int i=1;i<=n;i++){//初始化并查集结点
        p[i]=i;}for(int i=0;i<m;i++){//输入边int u,v,w;
        cin>>u>>v>>w;
        edges[i]={u,v,w};}sort(edges,edges+m);//按边权重从小到大将每条边排序int ans=0,cnt=0;//ans存储最小生成树边权重之和，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)){//如果a，b不在一个集合中，则合并它们
            p[find(a)]=find(b);
            ans+=w;
            cnt++;}}if(cnt<n-1) cout<<"impossible";//如果边数小于n-1，则最小生成树不存在else cout<<ans;return0;}

代码2

#include<iostream>#include<algorithm>usingnamespace std;constint N=200010;int n,m;int p[N];//并查集祖宗结点数组//结构体存储每条边structEdge{int a,b,w;}edges[N];//手写比较函数，使sort能够为结构体排序boolcmp(Edge A,Edge B){return A.w<B.w;}//并查集查找组总结点操作intfind(int x){if(p[x]!=x) p[x]=find(p[x]);return p[x];}intmain(){
    cin>>n>>m;for(int i=1;i<=n;i++){//初始化并查集结点
        p[i]=i;}for(int i=0;i<m;i++){//输入边int u,v,w;
        cin>>u>>v>>w;
        edges[i]={u,v,w};}sort(edges,edges+m,cmp);//按边权重从小到大将每条边排序int ans=0,cnt=0;//ans存储最小生成树边权重之和，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)){//如果a，b不在一个集合中，则合并它们
            p[find(a)]=find(b);
            ans+=w;
            cnt++;}}if(cnt<n-1) cout<<"impossible";//如果边数小于n-1，则最小生成树不存在else cout<<ans;return0;}

十三、染色法判别二分图

二分图当前仅当图中含奇数环

核心模板

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

int n;//n表示点数int h[N],e[M],ne[M],idx;//邻接表存储图int color[N];//表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色//参数：u表示当前结点，c表示当前点的颜色booldfs(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))returnfalse;}elseif(color[j]==c)returnfalse;}returntrue;}boolcheck(){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;}

题目链接： 860. 染色法判定二分图

13.1题目描述

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

13.2思路分析

使用染色法判定二分图：相邻点一定是不同的颜色。注意细节，具体思想见注释部分。

13.3代码实现

#include<iostream>#include<cstring>usingnamespace std;constint N=100010,M=2*N;//存储的是无向边，存储两次，所以得是点数的二倍int h[N],e[M],ne[M],idx;//邻接表存储图int color[N];int n,m;//邻接表加边voidadd(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;}//dfs进行染色booldfs(int u,int c){//u代表当前点的编号，c代表当前点的颜色：-1代表没染色，0代表为白色，1代表为黑色
    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))returnfalse;//如果该相邻点不能被染成与其不同的颜色，则无法完成染色}elseif(color[j]==c)returnfalse;//如果其相邻点和其为相同颜色，则无法完成染色}returntrue;}//判断每个点是否能够完成染色boolcheck(){memset(color,-1,sizeof color);//记得初始化for(int i=1;i<=n;i++){if(color[i]==-1){if(!dfs(i,0))returnfalse;//如果存在点无法完成染色，则不是二分图}}returntrue;}intmain(){
    cin>>n>>m;memset(h,-1,sizeof h);//记得初始化while(m--){int u,v;
        cin>>u>>v;add(u,v),add(v,u);}bool flag=check();if(flag) cout<<"Yes";else cout<<"No";return0;}

十四、匈牙利算法

核心模板

时间复杂度是O(nm)，n表示点数，m表示边数

int n1,n2;//n1表示第一个集合中的点数，n2表示第二个集合中的点数int h[N],e[M],ne[M],idx;//邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边int match[N];//存储第二集合中的每个点当前匹配的第一个集合中的点是哪个bool st[N];//表示第二个集合中的每个点是否已经被遍历过boolfind(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;returntrue;}}}returnfalse;}//求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点int res=0;for(int i=1;i<=n1;i++){memset(st,false,sizeof st);if(find(i)) res++;}

• 下图来自AcWing官网，作者们如图，侵权删。

题目链接：861. 二分图的最大匹配

14.1题目描述

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

14.2思路分析

使用匈牙利算法：枚举第一个集合中的点，每次都在第二个集合中找是否存在和它能够匹配成功的点，如果存在，结果加1。如果遇到第一个集合中的点在第二个集合中应该和它匹配的点已经被匹配了，就尝试是否可以使已经与第二个集合中的点匹配的第一个集合中的点换一个匹配点，如果可以，则将原匹配拆散，更新为新匹配，将当前枚举的点与拆散后的第二个集合中的点匹配；如果不可以，则该点无法完成匹配。

注意：“数据保证任意一条边的两个端点都不可能在同一部分中”即数据保证图是一个二分图，如果存在1到1的边，不是自环，而是从第一部分中的1指向第二部分中的1。

14.3代码实现

#include<iostream>#include<cstring>usingnamespace std;constint N=510,M=100010;int h[N],e[M],ne[M],idx;//邻接表存储每条边int n1,n2,m;int match[N];//存储当前与第二个集合匹配的第一个集合中的点是哪个bool st[N];//存储第二个集合中的点是否已经被遍历过//邻接表加边voidadd(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;}//查找是否存在与x匹配的点boolfind(int x){//枚举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;//则将原匹配拆散，j的新匹配为xreturntrue;}}}returnfalse;}intmain(){
    cin>>n1>>n2>>m;memset(h,-1,sizeof h);//记得初始化while(m--){int u,v;
        cin>>u>>v;add(u,v);}int ans=0;//枚举第一个集合中的每个点，看其是否能够匹配成功for(int i=1;i<=n1;i++){memset(st,false,sizeof st);//每次都先将第二个集合中的所有点设置为未遍历过，因为当前枚举的点要查看所有可以与其匹配的点是否能够和它匹配，而这些可以与它匹配的点可能也和其它的第一个集合中的点存在可匹配关系，所以每次都要清空st[]if(find(i)) ans++;//如果该点存在可以匹配的点，答案+1}
    cout<<ans;return0;}

补充题目

• 下述题目均来自蓝桥官网，侵删。

题目一

题目链接：
长草

1.1题目描述

1.2思路分析

利用bfs进行搜索，注意怎样控制扩展k层：第一次，首先把可以扩展的点放入队列中，然后在bfs中循环k次，每次都把队列中的元素进行拓展，注意只拓展队列中的元素，而且只拓展元素的数量次，所以循环的条件就是：第i次循环开始是队列中存在多少个可以拓展的点，就拓展多少次，（注意和一般宽搜条件不同，宽搜的条件是一直往外扩展，所以其条件是队列不空就往外拓展，这道题由于要控制拓展次数，所以我们的循环条件是外层循环开始时队列中有的元素个数）。

1.3代码实现

#include<iostream>#include<queue>#include<utility>usingnamespace std;typedef pair<int,int> PII;constint N=1010;int dx[]={1,-1,0,0},dy[]={0,0,1,-1};//方向数组
queue<PII> q;char g[N][N];int n,m,k;voidbfs(){while(k--){//拓展k次int cnt=q.size();//利用cnt控制，每次只拓展队列中已有的元素，新加入的不拓展，属于下一次拓展的点while(cnt--){
       PII t=q.front();//宽搜   
       q.pop();for(int i=0;i<4;i++){int a=t.first+dx[i],b=t.second+dy[i];if(a>=0&&a<n&&b>=0&&b<m&&g[a][b]=='.'){
             g[a][b]='g';
             q.push({a,b});}}}}}intmain(){  cin>>n>>m;for(int i=0;i<n;i++){for(int j=0;j<m;j++){
       cin>>g[i][j];if(g[i][j]=='g') q.push({i,j});//将最初的可以拓展的点加入队列}}
   cin>>k;bfs();//注意，别忘记调用函数for(int i=0;i<n;i++){for(int j=0;j<m;j++){
       cout<<g[i][j];}
     cout<<endl;}return0;}

注：本题也可参考我的这篇文章

题目二

题目链接：
排列序数

2.1题目描述

2.2思路分析

dfs搜索所有情况，每次搜索到一种情况，将对应的序号记录在哈希表中，之后进行查找即可。（或者直接当找到该种情况直接输出，然后结束程序即可，即

exit(0)

）

2.3代码实现

#include<iostream>#include<unordered_map>#include<string>usingnamespace std;constint N=15;bool st[N];
string s;int idx,len;voiddfs(int u,string path){if(u==len){if(path==s){
         cout<<idx;exit(0);//找到结束程序}
     idx++;return;}for(int i=0;i<len;i++){if(!st[i]){char in=char('a'+i),tmp=path[u];
         path[u]=in;
       st[i]=true;dfs(u+1,path);   
       st[i]=false;
       path[u]=tmp;}}}intmain(){  cin>>s;
   len=s.size();dfs(0,s);return0;}

隐藏回溯

#include<iostream>#include<unordered_map>#include<string>usingnamespace std;constint N=15;bool st[N];
string s;int idx,len;voiddfs(int u,string path){if(u==len){if(path==s){
         cout<<idx;exit(0);}
     idx++;return;}for(int i=0;i<len;i++){if(!st[i]){char in=char('a'+i);
       st[i]=true;dfs(u+1,path+in);//隐藏回溯，dfs完path的值没有变
       st[i]=false;}}}intmain(){  cin>>s;
   len=s.size();dfs(0,"");return0;}

注：本题也可参考我的这篇文章