算法基础课-搜索与图论

DFS

题目链接:842. 排列数字 - AcWing题库
思路:写的很好的题解AcWing 842. 排列数字--深度优先遍历代码+注释 - AcWing

#include<bits/stdc++.h>

using namespace std;
int n;
int st[10];
vector<int> a;
void dfs(){
    if(a.size() == n){
        for(int i=0;i<n;i++){
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
    for(int i=1;i<=n;i++){
        if(!st[i]){
            
            a.push_back(i);
            st[i] = true;
            dfs();
            a.pop_back();
            st[i] = false;
            
        }
    }
}

int main()
{
    cin>>n;
    dfs();
    
    return 0;
}

也可以考虑使用c++自带的next_permutation函数直接秒了:

#include<bits/stdc++.h>
using namespace std;
vector<int> a;
int n;
int st[10];

int main(){
	cin>>n;
	for(int i=0;i<n;i++) st[i] = i+1;
	do{
		for(int i=0;i<n;i++) cout<<st[i]<<" ";
		cout<<endl;
	}while(next_permutation(st,st+n));
	return 0;
} 

BFS

题目链接:844. 走迷宫 - AcWing题库

思路:由于bfs是一层一层扩展,所以能保证走到终点时,走过的距离最短,所以不需要取min。可以在bfs中判断一下,走到终点直接输出终点的distance。

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
int n,m;
const int N = 110;
int g[N][N];
int dist[N][N];
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
// int st[N][N];
void bfs(int x,int y){
    queue<PII> q;
    q.push({x,y});
    dist[0][0] = 0;
    // st[x][y] = true;
    while(q.size()){
        auto t = q.front();
        q.pop();
        int x = t.x,y = t.y;
        for(int i=0;i<4;i++){
            int tx = x + dx[i];
            int ty = y + dy[i];
            if(g[tx][ty] == 1) continue;
            if(tx<0||tx>=n||ty<0||ty>=m) continue;
            // if(st[tx][ty]) continue;
            // st[tx][ty] = true;
            g[tx][ty] = 1;
            dist[tx][ty] = min(dist[tx][ty],dist[x][y]+1);
            q.push({tx,ty});
            // cout<<tx<<" "<<ty<<endl;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++) cin>>g[i][j];
    }
    memset(dist,0x3f,sizeof dist);
    bfs(0,0);
    cout<<dist[n-1][m-1];
    return 0;
}

树与图的深度优先遍历

题目链接:1207. 大臣的旅费 - AcWing题库

思路:题意是求树的直径(树中两个最远结点的距离),可以随机找一个点0,走到距离0点最远的点1,再从这个点1走到距离点1最远的点2,此时点1距离点2的距离就是树的直径。

图的存储与遍历参考:B02 图的存储_哔哩哔哩_bilibili

#include<bits/stdc++.h>
#define x first 
#define y second 

using namespace std;
const int N = 100010;
typedef pair<int,int> PII;
vector<PII> h[N];
int dist[N];
void dfs(int u,int father,int distance){
    dist[u] = distance;
    
    for(auto t:h[u]){
        if(t.x!=father){
            dfs(t.x,u,distance+t.y);
        }
    }
    
}

int main(){
    int n ;
    cin>>n;
    for(int i=0;i<n-1;i++){
        int x,y,d;
        cin>>x>>y>>d;
        h[x].push_back({y,d});
        h[y].push_back({x,d});
    }
    
    dfs(1,-1,0);
    int u = 1;
    for(int i=1;i<=n;i++){
        if(dist[i]>dist[u]){
            u = i;
        }
    }
    dfs(u,-1,0);
    for(int i=1;i<=n;i++){
        if(dist[i]>dist[u]){
            u = i;
        }
    }
    
    int s = dist[u];

    printf("%lld\n", s * 10 + s * (s + 1ll) / 2);

    return 0;
}

树与图的广度优先遍历

题目链接:847. 图中点的层次 - AcWing题库

思路:h数组表示邻接表,下标表示结点编号,每个vector存储的是每个结点能到达的节点。

这个老师讲的超级好。B02 图的存储_哔哩哔哩_bilibili

#include<bits/stdc++.h>

using namespace std;
const int N = 100010;
vector<int> h[N];
bool st[N];
int dist[N];
int n,m;
void bfs(int u){
    queue<int> q;
    q.push(u);
    st[u] = true;
    dist[u] = 0;
    while(q.size()){
        int t = q.front();
        q.pop();
        if(t == n){
            cout<<dist[t];
            return;
        }
        for(int i=0;i<h[t].size();i++){
            int ne = h[t][i];
            if(st[ne]) continue;
            
            st[ne] = true;
            q.push(ne);
            dist[ne] = dist[t] + 1;
        }
    }
    cout<<-1<<endl;
    return;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        h[a].push_back(b);
    }
    memset(dist,-1,sizeof dist);
    bfs(1);
    return 0;
}

拓扑排序

题目链接:848. 有向图的拓扑序列 - AcWing题库
思路:跟bfs有些相似,先找入度为零的点加入到队列当中,再枚举当前结点出边,减少出边元素的入度,当入度为0时加入到拓扑序列中,这里是当出队的时候加入到序列中,跟bfs更像了。

这个老师讲的可好D01 拓扑排序_哔哩哔哩_bilibili。

#include<bits/stdc++.h>

using namespace std;
const int N = 100010;
vector<int> e[N],tp;
int din[N];

int n,m;
bool topsort(){
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(din[i] == 0) q.push(i);
    }
    while(q.size()){
        auto t = q.front();
        q.pop();
        tp.push_back(t);
        for(auto y : e[t]){
            din[y]--;
            if(!din[y]) q.push(y);
        } 
    }
    return tp.size() == n;
}

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        e[a].push_back(b);
        din[b]++;
    }
    if(topsort()){
        for(int i = 0;i<n;i++){
            cout<<tp[i]<<" ";
        }
    }else cout<<-1<<endl;
    
    return 0;
}

Dijkstra

朴素版

题目链接:849. Dijkstra求最短路 I - AcWing题库
思路:采取贪心的策略,对当前能到达的路径最短的点,使用其进行更新距离操作。

D02 最短路 Dijkstra 算法_哔哩哔哩_bilibili

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 510;
const int M = 1e5+10;
vector<PII> e[N];
int dist[N];
int n,m;
bool st[N];
void dijkstra(int s){
    dist[s] = 0;
    
    for(int i=1;i<n;i++){
        int u = 0;
        for(int i=1;i<=n;i++){
            if(!st[i]&&(dist[i]<dist[u] || u == 0)) u = i;
        }
        // cout<<u<<endl;
        st[u] = true;
        for(auto pr : e[u]){
            int v = pr.x, w = pr.y;
            if(dist[v]>dist[u]+w){
                dist[v] = dist[u] + w;
            }
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,w;
        cin>>a>>b>>w;
        e[a].push_back({b,w});
    }
    memset(dist,0x3f,sizeof dist);
    dijkstra(1);
    if(dist[n] == 0x3f3f3f3f) cout<<-1<<endl;
    else cout<<dist[n]<<endl;
    return 0;
}

堆优化版本

题目链接:850. Dijkstra求最短路 II - AcWing题库

思路:每次选秀选出当前最小的点,朴素版需要遍历寻找,堆优化版使用优先队列维护当前没有遍历到的距离最小的点,将每次选秀的遍历替换成取队列头部元素,从而降低时间复杂度。

需要注意的是为了维护优先队列中的顺序,存储的距离为负数。

D02 最短路 Dijkstra 算法_哔哩哔哩_bilibili

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
int n,m;
typedef pair<int,int> PII;
const int N = 150010, M = 150010;
int dist[N];
priority_queue<PII> q;
vector<PII> h[N];
bool st[N];
void dijkstra(int s){
    dist[s] = 0;
    q.push({0,s});
    while(q.size()){
        PII p = q.top();
        int u = p.y;
        q.pop();
        if(st[u]) continue;
        st[u] = true;
        for(auto t : h[u]){
            int v = t.x, w = t.y;
            if(dist[v]>dist[u] + w){
                dist[v] = dist[u] + w;  //忘记更新距离
                q.push({-(dist[u]+w),v});
            }
        }
        
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        h[a].push_back({b,c});
    }
    memset(dist,0x3f,sizeof dist);
    dijkstra(1);
    if(dist[n] == 0x3f3f3f3f) cout<<-1<<endl;
    else cout<<dist[n]<<endl;
    return 0;
}

bellman-ford

spfa

Floyd

题目链接:854. Floyd求最短路 - AcWing题库

思路:D04 最短路 Floyd 算法_哔哩哔哩_bilibili

#include<bits/stdc++.h>
using namespace std;
const int N = 210,INF = 1e9;
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;
	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,c;
		cin>>a>>b>>c;
		d[a][b] = min(d[a][b],c);
	}
	floyd();
	while(Q--){
		int a,b;
		cin>>a>>b;
		int t = d[a][b];
		if(t>INF/2) cout<<"impossible"<<endl;
		else cout<<t<<endl;
	}
	return 0;
}

Prim

题目链接:858. Prim算法求最小生成树 - AcWing题库

思路:D07 最小生成树 Prim 算法_哔哩哔哩_bilibili

和dijkstra一样,n次循环,每次选取最近的点来更新距离。

#include<bits/stdc++.h>
using namespace std;
const int N = 510,INF = 0x3f3f3f3f;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
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;
}

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();
	if(t==INF) cout<<"impossible"<<endl;
	else cout<<t<<endl;
	return 0;
}

Kruskal

题目链接:859. Kruskal算法求最小生成树 - AcWing题库

思路:Kruskal算法是根据边求取最小生成树,先按边权排序,依次取权重最小的边,查看边的起点和终点是否在同一集合中(使用并查集),若不在同一集合,则将边加入到答案中,若在同一集合则继续循环。D08 最小生成树 Kruskal 算法_哔哩哔哩_bilibili

需要注意的是重载小于号的操作要记一下。

#include<bits/stdc++.h>
// #define x first
// #define y second
using namespace std;
// typedef pair<int,int> PII;
int n,m;
const int N = 1e5+10,M = 2e5+10;
struct edge{
    int u;int v;int w;
    bool operator<(const edge &t)const{
        return w<t.w;
    }
}e[M];
// vector<edge> e;
int fa[N];
int find(int x){
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        e[i] = {a,b,c};
    }
    int ans = 0;
    int cnt = 0;
    sort(e,e+m);
    for(int i=1;i<=n;i++) fa[i] = i;
    for(int i=0;i<m;i++){
        int u = e[i].u;
        int v = e[i].v;
        int w = e[i].w;
        if(find(u)!=find(v)){
            ans += w;   
            fa[find(u)] = find(v);
            cnt++;
        }
    }
    if(cnt == n-1) cout<<ans<<endl;
    else cout<<"impossible"<<endl;
    
    return 0;
}

染色法判定二分图

题目链接:860. 染色法判定二分图 - AcWing题库
思路:二分图的意思是看是否有能将所有节点分成两块,每块的节点中不能直接相连这样的情况存在。如下图中的1,4和2,3,5。根据定理:二分图中不存在奇环,我们可以由此判别一个图是否是二分图。D24 二分图判定 染色法_哔哩哔哩_bilibili

老师使用的是链式前向星存储的图结构,具体思路如下。感觉直接用邻接表存储更好想,也更简便。

#include<bits/stdc++.h>

using namespace std;
int n,m;
const int N = 100010,M = 100010;
vector<int> h[N];
int color[N];
bool dfs(int u,int c){
    color[u] = c;
    for(auto t : h[u]){
        if(!color[t]){
            if(dfs(t,3-c)) return 1;
        }else if(color[t] == c) return 1;
    }
    return 0;
}

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        h[a].push_back(b);
        h[b].push_back(a);
    }
    bool flag = false;
    for(int i =1;i<=n;i++){
        if(!color[i]){
            if(dfs(i,1)){
                flag = 1;
                break;
            }
        }
    }
    if(flag) puts("No");
    else puts("Yes");
    return 0;
    
}

匈牙利算法

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/521395.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

python标准数据类型--集合常用方法

在Python中&#xff0c;集合&#xff08;Set&#xff09;是一种无序且不重复的数据结构&#xff0c;它是由一个无序的、不重复的元素组成的。Python中的集合与数学中的集合概念相似&#xff0c;并且支持一系列常用的方法。本篇博客将深入介绍Python集合的常用方法&#xff0c;帮…

c# wpf XmlDataProvider 简单试验

1.概要 2.代码 <Window x:Class"WpfApp2.Window12"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schemas.microsoft.com/expression/blend…

【C++初阶】String在OJ中的使用(一):仅仅反转字母、字符串中的第一个唯一字母、字符串最后一个单词的长度、验证回文串、字符串相加

前言&#xff1a; &#x1f3af;个人博客&#xff1a;Dream_Chaser &#x1f388;博客专栏&#xff1a;C &#x1f4da;本篇内容&#xff1a;仅仅反转字母、字符串中的第一个唯一字母、字符串最后一个单词的长度、验证回文串、字符串相加 目录 917.仅仅反转字母 题目描述&am…

C#操作MySQL从入门到精通(5)——查询数据

前言 在和MySql数据库交互的过程中,查询数据是使用最频繁的操作,本文详细介绍了查询数据的各种操作,包括查询一列数据、 查询两列数据、查询所有列数据、查询不重复的数据、查询指定行数据,绝对是C#操作MySql数据库史上最详细教程,能够帮助小白快速入门以及将这些功能迅速…

【数据结构】考研真题攻克与重点知识点剖析 - 第 3 篇:栈、队列和数组

前言 本文基础知识部分来自于b站&#xff1a;分享笔记的好人儿的思维导图与王道考研课程&#xff0c;感谢大佬的开源精神&#xff0c;习题来自老师划的重点以及考研真题。此前我尝试了完全使用Python或是结合大语言模型对考研真题进行数据清洗与可视化分析&#xff0c;本人技术…

阿里云2核2G和2核4G轻量应用服务器优惠价格表,2024年最新报价

阿里云轻量应用服务器2核2G和2核4G配置优惠价格表&#xff0c;轻量2核2G3M带宽61元一年&#xff0c;轻量2核4G4M带宽165元1年&#xff0c;均不限制月流量&#xff0c;阿里云活动链接 aliyunfuwuqi.com/go/aliyun 活动打开如下图&#xff1a; 阿里云轻量应用服务器价格 61元/年…

上位机图像处理和嵌入式模块部署(qmacvisual实时视频)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 前面我们测试和练习的时候&#xff0c;大部分情况下都是利用图像进行测试的&#xff0c;但是实际情况下&#xff0c;或者准确一点说&#xff0c;工…

android 制作登录页

项目需要可以直接copy layout.xml <?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"…

【六 (2)机器学习-EDA探索性数据分析模板】

目录 文章导航一、EDA&#xff1a;二、导入类库三、导入数据四、查看数据类型和缺失情况五、确认目标变量和ID六、查看目标变量分布情况七、特征变量按照数据类型分成定量变量和定性变量八、查看定量变量分布情况九、查看定量变量的离散程度十、查看定量变量与目标变量关系十一…

软考114-上午题-【计算机网络】-路由

一、路由 二、真题 真题1&#xff1a; 真题2&#xff1a; 真题3&#xff1a; 真题4&#xff1a; 真题5&#xff1a; 路由协议实际上是一种在路由器之间交换路由信息的协议。 路由协议让路由器了解整个网络的拓扑结构&#xff0c;包括哪些网络是直接相连的&#xff0c;哪些网络…

vscode的源码插件GitHub Repositories

打铁还需自身硬&#xff0c;需要不断提升自我&#xff0c;提升自我的一种方式就是看源码&#xff0c;站在更高的维度去理解底层原理&#xff0c;以便以后更好的开发和解决问题&#xff0c;由于源码一个动不动就是几个G甚至十几个G&#xff0c;如果一个个源码下载下来&#xff0…

LeetCode刷题之31.下一个排列

文章目录 1. 题目2.分析3.解答3.1 先排序&#xff0c;后交换3.2 先交换&#xff0c;后排序 1. 题目 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如&#xff0c;arr [1,2,3] &#xff0c;以下这些都可以视作 arr 的排列&#xff1a;[1,2,3]、[1,3,2]、[3…

睿考网:注册会计师科目搭配技巧

注册会计师考试共考六门&#xff0c;关于考试科目的具体搭配&#xff0c;考生可以根据自己的学习情况来进行合理搭配&#xff0c;睿考网为大家推荐常见的科目搭配&#xff1a; 报两科&#xff1a; 1. 《会计》《税法》 2. 《会计》《审计》 3. 《财务成本管理》《公司战略与…

如何从数码相机恢复已删除的照片?

“嗨&#xff0c;我删除了索尼数码相机中的所有照片。有什么办法可以让他们回来吗&#xff1f;” ——刘凯 我们经常从数码相机中删除照片。但是&#xff0c;如果我们误删除了一些重要的照片&#xff0c;则很难将其恢复&#xff0c;因为删除的照片可能会绕过回收站或垃圾箱&am…

SQL语句的编写

##创建用户-建表建库 #创建一个用户名为 feng&#xff0c;允许从任何主机 % 连接&#xff0c;并使用密码 sc123456 进行身份验证的用户。 rootTENNIS 16:33 scmysql>create user feng% identified by sc123456; Query OK, 0 rows affected (0.04 sec) #创建一个名为fen…

Golang | Leetcode Golang题解之第12题整数转罗马数字

题解&#xff1a; 题解&#xff1a; var (thousands []string{"", "M", "MM", "MMM"}hundreds []string{"", "C", "CC", "CCC", "CD", "D", "DC", "…

ARM v8 Cortex R52内核 02 程序模型 Programmers Model

ARM v8 Cortex R52内核 02 程序模型 Programmers Model 2.1 关于程序模型 Cortex-R52处理器实现了Armv8-R架构。这包括&#xff1a; 所有的异常级别&#xff0c;EL0-EL2。 每个异常级别下的AArch32执行状态。 T32和A32指令集&#xff0c;其中包括&#xff1a; 浮点运算。 …

数据结构--树和二叉树

树和二叉树 1.树概念及结构树的概念树的相关概念树的表示 2.二叉树概念及结构概念特殊的二叉树二叉树的性质 3.二叉树顺序结构及实现4.二叉树链式结构及实现二叉树的顺序结构二叉树的前&#xff0c;中&#xff0c;后序遍历层序遍历 1.树概念及结构 树的概念 树是一种非线性的…

我做的小程序,一下流量就爆了【小游戏:你对颜色敏感吗】

大家好&#xff0c;我是鬼哥&#xff0c;一位8年前端从业者&#xff0c;也是一位全栈开发&独立开发者&#xff0c; 最近有点浮躁&#xff0c;可笑的是2024年已经过去一个季度了&#xff0c;我今年的目标貌似都还没正式开始。 本来去年下半年计划今年开始&#xff0c;正式运…

Java集合——Map、Set和List总结

文章目录 一、Collection二、Map、Set、List的不同三、List1、ArrayList2、LinkedList 四、Map1、HashMap2、LinkedHashMap3、TreeMap 五、Set 一、Collection Collection 的常用方法 public boolean add(E e)&#xff1a;把给定的对象添加到当前集合中 。public void clear(…