1.【深基18.例3】查找文献
题目描述
小K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。
假设洛谷博客里面一共有 n(n<=10^5) 篇文章（编号为 1 到 n）以及 m(m<=10^6) 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。
这边是已经整理好的参考文献关系图，其中，文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。
请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。
输入格式
共 m+1 行，第 1 行为 2 个数，n 和 m，分别表示一共有 n(n<=10^5) 篇文章（编号为 1 到 n）以及m(m<=10^6) 条参考文献引用关系。
接下来 m 行，每行有两个整数 X,Y 表示文章 X 有参考文献 Y。
输出格式
共 2 行。
第一行为 DFS 遍历结果，第二行为 BFS 遍历结果。
样例 #1
样例输入 #1
8 9
1 2
1 3
1 4
2 5
2 6
3 7
4 7
4 8
7 8
样例输出 #1
1 2 5 6 3 7 8 4
1 2 3 4 5 6 7 8
这道题本质就是考bfs与dfs,只是以图作为一个载体。所以，我们只需要知道bfs与dfs的基本步骤就可以简单地通过了。~~（好像也没那么简单）~~要注意的就是怎么存图了。这里的数据达到了10^5，所以显然不可以用邻接矩阵来存，可以考虑用vector或者链式前向星存图。这里我采用vector。
完整注释代码如下：
#include<bits/stdc++.h>
using namespace std;
#define maxn1 100005
#define maxn2 1000005
struct que{
int head;
int tail;
int nums[maxn1];
}q; //手写队列，最为致命qwq
vector<int>g[maxn1]; //vector存图
int n,m;
bool book[maxn1]; //标记数组
void dfs(int now){ //深搜
int next;
for(int i=0;i<g[now].size();i++){
next=g[now][i];
if(!book[next]){
cout<<next<<" ";
book[next]=1;
dfs(next); //不用回溯
}
}
}
int main(){
cin>>n>>m;
int u,v,now,next;
for(int i=1;i<=m;i++){
cin>>u>>v;
g[u].push_back(v); //vector存图
}
for(int i=1;i<=n;i++){
sort(g[i].begin(),g[i].end()); //记得要排序
}
book[1]=1; //初始化起点为标记过的
cout<<"1 "; //直接输出起点
dfs(1);
memset(book,0,sizeof(book)); //在dfs后还要bfs，所以再次全部清零
cout<<endl<<"1 "; //直接输出起点
book[1]=1;
q.nums[q.tail++]=1; //将起点入队
while(q.head<q.tail){
int now=q.nums[q.head];
for(int i=0;i<g[now].size();i++){
next=g[now][i]; //遍历所有的边
if(!book[next]){
cout<<next<<" ";
book[next]=1;
q.nums[q.tail++]=next; //入队操作
}
}
q.head++; //记住队头一定要++,否则会死循环
}
return 0;
}
2.【模板】floyd
题目背景
模板题，无背景
题目描述
给出n个点，m条边的无向图，求每个点到其他点的距离之和%998244354的值
输入格式
第一行两个数n，m含义如上
从第二行开始，共m行，每行三个数x，y，l，代表从x到y点的长度为l
输出格式
n行，每行一个数，第i行代表点i到其他点的距离之和
样例 #1
样例输入 #1
2 1
1 2 4
样例输出 #1
4
4
样例 #2
样例输入 #2
4 5
1 2 1
1 3 2
2 3 2
3 4 3
2 4 4
样例输出 #2
8
7
7
12
提示
模板题，保证图联通
n<=500
m<=10000
1<=x,y<=n
l<=1e9
考floyd算法的一道模板题。floyd算法具有动态规划的思想，这里我用简单易懂的语言解释一下这个算法。设f(i,j)为从i点直接到达j点的距离，那么转态转移方程为:
f
(
i
,
j
)
=
m
i
n
(
f
(
i
,
j
)
,
f
(
i
,
k
)
+
f
(
k
,
j
)
)
1
≤
k
≤
n
f(i,j)=min(f(i,j),f(i,k)+f(k,j)) \quad 1\leq k\leq n
f(i,j)=min(f(i,j),f(i,k)+f(k,j))1≤k≤n
其实我们可以把它看成从i点到j点通过k点中转是否会让距离缩短，如果会就更新f(i,j)，否则就保留。
但是这个算法的时间复杂度有一点点大，是O(n^3)，虽然代码简单，但是一般不用。但是因为这道题的名字都叫floyd了，那么肯定是要用的。
但是，这道题的难点（坑点）并不在这里，最难（坑）的地方是，这m条边里是有重边的，我们要取其中较短的那一条边。（这一开始谁会想到啊，害我一直看我的floyd算法代码哪里错了,直接卡了一个多小时）
完整代码如下:
#include<bits/stdc++.h>
using namespace std;
#define maxn1 5005
#define maxn2 99999999999 //无穷大
#define mod 998244354
long long mat[maxn1][maxn1],ans[maxn1];
int n,m;
int main(){
cin>>n>>m;
long long u,v,w,now;
for(int i=1;i<=n;i++){
for(int a=1;a<=n;a++){
mat[i][a]=maxn2; //初始化矩阵
}
}
for(int i=1;i<=n;i++){
mat[i][i]=0; //自身初始化为0
}
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
mat[u][v]=min(w,mat[u][v]);
mat[v][u]=min(w,mat[v][u]); //有重边，要取较短的那一条
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int h=1;h<=n;h++){
mat[j][h]=min(mat[j][h],mat[j][i]+mat[i][h]); //只有4行的floyd算法
}
}
}
for(int i=1;i<=n;i++){
for(int a=1;a<=n;a++){
ans[i]=(ans[i]+mat[i][a])%mod; //求和时记得求余
}
}
for(int i=1;i<=n;i++){
if(i==n){
cout<<ans[i];
break;
}
cout<<ans[i]<<endl; //输出结果
}
return 0;
}
3.【模板】单源最短路径（标准版）
题目背景
2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程 一题里非常熟练地使用了一个广为人知的算法求最短路。
然后呢？
100 --> 60；
Ag --> Cu；
最终，他因此没能与理想的大学达成契约。
小 F 衷心祝愿大家不再重蹈覆辙。
题目描述
给定一个 n 个点，m 条有向边的带非负权图，请你计算从 s 出发，到每个点的距离。
数据保证你能从 s 出发到任意点。
输入格式
第一行为三个正整数 n, m, s。
第二行起 m 行，每行三个非负整数 u_i, v_i, w_i，表示从 u_i 到 v_i 有一条权值为 w_i 的有向边。
输出格式
输出一行 n 个空格分隔的非负整数，表示 s 到每个点的距离。
样例 #1
样例输入 #1
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
样例输出 #1
0 2 4 3
提示
样例解释请参考 数据随机的模板题。
1 <= n <= 10^5；
1 <= m <= 2* 10^5；
s = 1；
1 <=u_i, v_i<= n；
0 <= w_i <= 10 ^ 9,
0 <=sum (w_i) <= 10 ^ 9。
本题数据可能会持续更新，但不会重测，望周知。
2018.09.04 数据更新 from @zzq
一道考dijkstra算法的题目，这里我就不过多介绍这个算法了，我引用洛谷题解里的这位大佬的题解，他已经讲得十分详细了。~~（主要是因为懒）这里的数据较大，dijkstra算法原本是具有O(n^2)的时间复杂度的，所以，我们需要用堆来优化这个算法。c语言需要手写堆，但是，在c++中，我们有高贵的优先队列（priority_queue）（c++狂喜）~~所以，我们就可以将算法的时间复杂度降为O((n+m)log2n)。
那么dijkstra的步骤是什么呢?
- 1.初始化dis[start] = 0,dis[start]=0,其余节点的dis值为无穷大.
- 2.找一个dis值最小的蓝点x，把节点x变成白点.
- 3.遍历x的所有出边(x,y,z),若dis[y] > dis[x] + z,则令dis[y]=dis[x]+z
- 4.重复2,3两步,直到所有点都成为白点…
（其实就是那篇题解里的步骤）堆优化优化的是找到dis值最小的点的步骤。我们只需要让没有被标记的点进入优先队列（c++狂喜），那么优先队列自动就会为我们找到最小的那个点**(要开最小堆)**，所以，我们就可以很容易写出答案
完整注释代码如下:文章来源地址https://www.toymoban.com/news/detail-437082.html
#include<bits/stdc++.h>
using namespace std;
#define maxn1 10000000
#define maxx 1e9+5 //无穷大
int head[maxn1],tot,n,m,s;
bool book[maxn1]; //标记点是否进入队列
struct edge{
int v;
int w;
int next;
}e[maxn1]; //链式前向星
struct node{
int dis;
int pos;
bool operator <(const node &s2)const {
return s2.dis<dis; //让优先队列以距离为排序标准
}
};
int diss[maxn1];
void add(int u,int v,int w){ //添加的函数
e[++tot].v=v,e[tot].w=w,e[tot].next=head[u],head[u]=tot;
}
priority_queue<node>q; //c++狂喜
void d(){ //diljkstra算法实现
node temp;
int v,w;
diss[s]=0;
q.push({0,s}); //初始时让起点入队
while(!q.empty()){ //在队列不为空时循环
temp=q.top(); //找到最小点
q.pop(); //移除最小点
int x=temp.dis,y=temp.pos;
if(book[y]){
continue; //如果已经进集合了，就直接下一个
}
book[y]=1; //如果没有进集合，就标记它
for(int i=head[y];i;i=e[i].next){
v=e[i].v,w=e[i].w; //遍历所有边
if(diss[v]>diss[y]+w){
diss[v]=diss[y]+w; //边松弛
if(!book[v]){
q.push((node){diss[v],v}); //没有进集合就入队
}
}
}
}
}
int main(){
int u,v,w;
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
add(u,v,w); //添加边
}
for(int i=1;i<=n;i++){
diss[i]=maxx; //初始化都为无穷大
}
d();
for(int i=1;i<=n;i++){
cout<<diss[i]<<" "; //输出距离
}
return 0;
}
在图论题单里随便挑的一道题：(看上去比较简单的题，其他题都看不懂qwq)
4.【模板】并查集
题目描述
如题，现在有一个并查集，你需要完成合并和查询操作。
输入格式
第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。
接下来 M 行，每行包含三个整数 Z_i,X_i,Y_i 。
当 Z_i=1 时，将 X_i 与 Y_i 所在的集合合并。
当
Z
i
=
2
Z_i=2
Zi=2 时，输出 X_i 与 Y_i 是否在同一集合内，是的输出Y ；否则输出 N 。
输出格式
对于每一个 Z_i=2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。
样例 #1
样例输入 #1
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
样例输出 #1
N
Y
N
Y
提示
对于 30% 的数据，N < 10，M <20。
对于 70% 的数据，N < 100，M < 10^3。
对于 100% 的数据，1< N < 10^4，1< M < 2* 10^5，1 < X_i, Y_i < N，Z_i { 1, 2 }。
对于并查表，我引用洛谷题解里的这位大佬的题解简单解释一下。我们可以先设f[i]=j表示 i 的老大是 j 。那么我们在查找一个人的老大时可以调用一个find函数，如下:
int find(int x){
if(f[x]==x) return x;
else{
find(f[x]);
}
}
显然，我们在查找该人的老大时，我们会遍历该人头上所以的上级，那么我们同时将这些人的老大同时改为该人的老大呢?
那么我们的代码就会变成这样:
int find(int x){
if(f[x]==x) return x;
else {
return f[x]=find(f[x]);
} //路径压缩
}
所以我们在判断a和b是否在一个集合里时，就可以写成if(find(a)==find(b))。非常简单文章来源：https://www.toymoban.com/news/detail-437082.html
完整注释代码如下:
#include<bits/stdc++.h>
using namespace std;
int f[10005]; //f[i]=j表示i的老大是j
int find(int x){
if(f[x]==x) return x;
else{
return f[x]=find(f[x]);
}
//路径压缩
}
int main(){
int n,m,a,b,c;
cin>>n>>m;
for(int i=1;i<=n;i++){
f[i]=i;
}
for(int i=0;i<m;i++){
cin>>a>>b>>c;
if(a==1){ //b的老大变为c的老大
f[find(b)]=find(c);
}
else{ //判断b和c的老大是否相同
if(find(b)==find(c)){
cout<<"Y"<<endl;
}
else{
cout<<"N"<<endl;
}
}
}
return 0;
}
到了这里，关于week9-图论进阶（最短路径）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
