今天上午模拟赛的时候,(十分错误地)判断有一道题可以用LCA混点分(然而还不如直接爆搜得分高),在敲那个LCA的代码时突然想起来我好像还没有写过LCA,想了想,是该给我的LCA写点东西了呢。
但是!不出意外的,出了亿点点意外,就是我在敲板子题的时候发现经过一年的荒废,我已经完全不会链式前向星。好不容易捣鼓了半天,终于还是没调出来,于是我只能十分痛心疾首地去好好学习了一下。
所以!本来今天要说说LCA的,但是最终我决定还是先讲讲图论最最基础,也是最为致命(啊,就是说我因为不会链式前向星导致我没把LCA整出来)的东西之一,存图!
这里只介绍两种常用的方法,如有需要的的同学可以看看别人的拓展。
————————————–分割线———————————————
一,邻接矩阵
邻接矩阵顾名思义,是一个矩阵(废话),在老一点的算法书里面常常能见到用这种方法存图的代码。优点是特别简单好理解,用起来也是非常的方便;缺点在于空间复杂度是n^2级的。
举个例子吧,有如下无向连通图(每边边长为1)
首先我们要开一个数组f[mm][mm],其中f[i][j]表示点i到点j之间连边的长度,如下图
另外,很显然一个点到它自己的距离是零
因为这是一个无向图,所以存图的时候要注意f[i][j]=f[j][i]这一点,即,同一边要存两次;
如果说点i和点j之间没有直接的边那应该如何表示呢?很简单,初始化为inf,两个点之间距离无限远不就是说两点之间不能互相直接到达吗,所以见如下代码
1 #include
2 using namespace std;
3 const int mm=205;//并没有什么特殊意义
4 const int inf=1e9+7;
5 int f[mm][mm];
6 int n,m;//有n个点,m条边
7 int main()
8 {
9 cin>>n>>m;
10 for(int i=1;i)
11 for(int j=1;j)
12 {
13 f[i][j]=inf;//初始化为任意两点之间距离为inf
14 }
15 for(int i=1;i)
16 {
17 int x,y;
18 cin>>x>>y;//将两个点相连
19 f[x][y]=1;
20 f[y][x]=1;
21 }
22 return 0;
23 }
二、链式前向星
链式前向星近些年非常常见,它的诞生让图论题的数据范围大幅提高(真是太糟糕了),相比于邻接矩阵,链式前向星确实会更复杂、更难自己想(指的是我自己调半天都不知道问题在哪),但一个标准的链式前向星的代码量其实很少,占用的空间也会少得多
邻接矩阵实际上是基于点的存图,它储存的是点与点之间的连边,而链式前向星是基于边的存图,它储存的是一条条的边,每条边的两个端点分起点终点。
我们选择使用结构体(结构体介绍:https://www.cnblogs.com/qj-Network-Box/p/13138534.html)来实现存边的操作,一条边的要素,无非是起点终点和长度,由于上图每条边的长度一样,暂时先不考虑长度的问题
1 const int mm=205;//没有什么特别的意义
2 struct node{
3 int s,v;//从点s到点v
4 }a[mm];
很显然,链式前向星,身为一个用链开头的词,和链表多多少少有点联系
而这个联系就在于:同一起点的边被排成一条链。原因很显然,方便查询
我们回到这幅图
按照起点分类,可以变成以下几串
比如,要实现查询到点1到点2的路径后能找到点1到点3的路径,就可以在存点1到点2路径的结构体里面添加一个nex元素,nex指向下一个以1为起点的元素
那么问题来了,我们一开始怎么找到点1到点2的那条边呢(身为该起点被存入的第一条边,没有nex指向它),我们需要一个head[x]数组来存储起点为x的第一条边的序号
显然既然是同一起点的,在存边的时候就不需要把起点算进去了
const int mm=205;//没有什么特别的意义
struct node{
int v,nex;
}a[mm*2];
int head[mm];//用于储存最头部边的序号
考虑遍历,以x为起点的第一条边编号为head[x],下一条就应该是a[head[x]].nex,再下一条就是a[a[head[x]].nex].nex,直到某个节点的nex指向0
代码实现如下
#include
using namespace std;
int tot;
int n;
const int mm=205;//没有什么特别的意义
struct node{
int v,nex;//从点x到点v
}a[mm*2];
int head[mm];//用于储存第一条边的序号
void add(int x,int y) //一条x到y的边
{
a[++tot].v=y;//目标是y
a[tot].nex=head[x];//将上一条边的nex指向这一条边
head[x]=tot;//更新
}
void pp(int x)
{
for(int i=head[x];i!=0;i=a[i].nex)//以head[x]为第一边,每次跳转到nex所指的下一条边
{
cout }
return ;
}
int main()
{
cin>>n;
for(int i=1;i)
{
int x,y;
cin>>x>>y;
add(x,y),add(y,x);//无向图要存两边
}
for(int i=1;i {
pp(i);
}
return 0;
}
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
相关推荐: APP中RN页面热更新流程-ReactNative源码分析
平时使用WebStorm或VSCode对RN工程中的文件修改后,在键盘上按一下快捷cmd+s进行文件保存,此时当前调试的RN页面就会自动进行刷新,这是RN开发相比于原生开发一个很大的优点:热更新。 那么,从按一下快捷cmd+s到RN页面展示出最新的JS页面,这…