笨鸟先飞,一次学不会就再学一次

目录

笨鸟先飞,一次学不会就再学一次

一:图论

1:哥尼斯堡七桥问题(现在是俄罗斯的加里宁格勒)、

2: 图的基本概念。

CSDN上有很多,此处省略。

3:图的存储与遍历

a.可以用邻接矩阵实现

 b.邻接表

4:图的连通性问题

a.无向图DFS:

 d:Tarjan算法

5:LCA最近公共祖先

a:暴力法

b:倍增法

c:转化为RMQ问题

d:塔扬离线算法

6:最小生成树

二:搜索

1:收获:

a:笔算

b:看头文件源码

c:洛谷的讨论区非常有用

2:感受


一:图论

这一部分还没开始做题,刚开始看资料

以下是这周学习到的有关图论的知识

1:哥尼斯堡七桥问题(现在是俄罗斯的加里宁格勒)、

在哥尼斯堡(加里宁格勒) 的一个公园里, 有七座桥将普雷格尔河中两个岛及岛与河岸连接起来 . 问是否可能从这四块陆地中任一块出发, 恰好通过每座桥一次, 再回到起点?

由这个问题我得到了如果枚举每一种可能,就是7的阶乘,把该问题抽象成图,仔细阅读欧拉回路后得知,这个图的各个节点必须是联通的,和每个节点相连的线段必须是偶数,否则就不能回来。

2: 图的基本概念。

CSDN上有很多,此处省略。

3:图的存储与遍历

a.可以用邻接矩阵实现

用一个一维数组存储图中顶点的信息
,
用一个二维数组
(
矩阵
)
表示图中各顶点之
间的邻接关系
.
#define MAXN 100
int main()
{
int n, m, u, v, map[MAXN][MAXN];
memset(map, 0, sizeof(map));//初始化,元素清零
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++)
{
scanf("%d%d", &u, &v);
map[u-1][v-1] = 1; map[v-1][u-1] = 1;//无向图需要
}
//其它操作
return 0;
}

图的DFS遍历是很多算法的基础,所以一定要掌握好DFS;

 邻接矩阵的特点:

 空间复杂度:O(n2)

 可以O(1)查询点对间的边数(或相邻情况)

邻接矩阵的缺点:空间复杂度大,处理稀疏图效率低,不便于处理多 重图边上的附加信息。

 b.邻接表

邻接表可以用四种方式去实现,第一种是动态链表,第二种是用vector实现。第三种是用静态链表实现也就是纯数组实现,第四种是链表+静态分配节点(数组)实现。

邻接表的特点:  

  1. 空间复杂度:O(n+m)
  2. 可以高效的访问结点的所有邻接边(结点)
  3.  可以很好的处理重边
  4. 无法高效查询任意点对间的信息

代码示例:

动态链表:

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100
struct edge { //边结构体
int nodeid;
int edge_value;
struct edge* next;
};
struct node { //结点结构体
//int node_value;
struct edge* next;
}mynode[MAXN];
int main() {
int n, m, u, v, w;
edge* newedge;
scanf("%d%d", &n, &m);
memset(mynode, 0, sizeof(mynode));
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &w);
newedge = new edge; //建新边
newedge->nodeid = v; //记录边的一个端点
newedge->edge_value = w; //记录边权
newedge->next = mynode[u].next; //插入到u的邻接边中
mynode[u].next = newedge;
//若是无向图,则添加对称边
newedge = new edge;
newedge->nodeid = u;
newedge->edge_value = w;
newedge->next = mynode[v].next;
mynode[v].next = newedge; }
//其它操作
return 0;
}

vector实现:

vector<vector<int> > mynode(5); 
for(int i = 0; i < 10; i++)
{
scanf("%d%d", &u, &v);
mynode[u].push_back(v);
}
#include <bits/stdc++.h>
using namespace std;
struct edge {
int nodeid, value;
};
int main() {
int n, m, u, v, w; edge temp;
scanf("%d%d", &n, &m);
vector<vector<edge> > mynode(n); // > >必须有空格
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &w);
temp.nodeid = v; temp.value = w;
mynode[u].push_back(temp);
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < mynode[i].size(); j++)
printf("%d-%d(%d) ", i, mynode[i][j].nodeid, mynode[i][j].value);
printf("\n");
}
return 0;
}
//cin
/*
4 4
3 0 8
2 3 5
0 2 3
0 1 6
*/

纯数组实现:

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100
#define MAXM 1000
//本例代码针对有向图
int main() {
int n, m, u, v;
int node[MAXN], id[MAXM], w[MAXM], next[MAXM];
memset(node, -1, sizeof(node));
memset(next, -1, sizeof(next));
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++) {//i是边的编号
scanf("%d%d%d", &u, &v, &w[i]);
id[i] = v;
next[i] = node[u];
node[u] = i; }
//其它操作
return 0;
}
//假设要遍历结点u的所有邻接边
int e = node[u];
while(e != -1) {
printf("%d ", w[e]);
e = next[e];
}

链表+数组:


#include <bits/stdc++.h>
using namespace std;
#define MAXN 100
#define MAXM 1000
struct edge {
int nodeid;
int edge_value;
struct edge* next;
}myedge[MAXM];
struct node {
//int node_value;
struct edge* next;
}mynode[MAXN];
int main() {
int k = 0, n, m, u, v, w;
scanf("%d%d", &n, &m);
memset(mynode, 0, sizeof(mynode));
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &w);
newedge[k].nodeid = v;
newedge[k].edge_value = w;
newedge[k].next = mynode[u].next;
mynode[u].next = &newedge[k];
k++;
//若是无向图,则
newedge[k].nodeid = u;
newedge[k].edge_value = w;
newedge[k].next = mynode[v].next;
mynode[v].next = &newedge[k];
k++;
}
//其它操作
return 0;
}

//假设要遍历结点u的所有邻接边
struct edge* e = mynode[u].next;
while(e != NULL) {
printf("%d ", e->edge_value);
e = e->next;
}

[HNOI2003]消防局的设立 - 洛谷

这个例题有点难,我看不懂

4:图的连通性问题

分为无向图和有向图,其中,无向图可以采用查并集和DFS两种算法,查并集可以用来判断连通分支是否为一个树

a.无向图DFS:

对于一个没有访问过的点, 从这个点开始DFS, 访问所有还没有访问过的点, 每访问到一个点, 就将其标记为已访问. 在某一个点DFS结束时, 所有在这一轮访问到的点就在一个连通分量中. 该算法的时间复杂度为O(n+m).

b.无向图查并集

扫描所有的边, 不断合并两个连通分量. 该算法的时间复杂度也为O(n+m)

c.有向图暴力求解

时间复杂度是O(N*M)比较的高

先利用深度优先搜索或宽度优先搜索, 可以得到每个结点能到达的结点.

 再利用原图结点构造一个新的无向图. 两个结点加边当且仅当互达.

 最后新图(无向图)的连通分量就对应着原图的强连通分量.

 d:Tarjan算法

暂时没看懂

5:LCA最近公共祖先

有四个算法,分别是暴力法,倍增法,转化为RMQ问题,Tarjan离线算法

a:暴力法

采取两个点逐渐向根移动的方法, 求出LCA. 具体步骤:
(1)求出每个结点的深度;
(2)询问两个结点是否重合, 若重合, 则LCA已求出.
(3)否则, 选择两个点深度较大的一个移动到它的父亲.
重复执行(2)(3)步.
该算法最坏情况可达O(n), 但实现简单, 如果树是随机的或者树的深度不大, 可以使用该算法

int getlca(int x, int y) {
while(x != y) {
if(de[x] >= de[y]) x = fa[x];
else y = fa[y];
}
return x;
}

b:倍增法

本算法是暴力法的改进核心是让两个节点每次向上走2步的幂次步。

(1)定义并求出倍增数组anc[maxn][maxlog]. 其中maxlog是最小的满足2x >= MaxDeep的x, anc[i][j]为结点i向上走2j步后能走到的结点. 规定根结点的父亲是它自己. 这样根节点往上走还是在根结点. 对于j = 0, anc[i][j]就是结点i的父亲. 对于j > 0, anc[i][j]等于anc[anc[i][j-1]][j-1](即结点i往上走2j-1步后再往上走2j-1步).
(2)把两个点移到同一深度. 令de[x] >= de[y] (否则交换x,y), 先让x往上走de[x] - de[y]步. 将这个差表示成二进制, 就可以通过倍增数组往上走2的幂次步(即对于二进制为1的第i位. 要往上走2i步, 调用x = anc[x][i], 那么可以在O(log2n)的时间复杂度内到达目标深度. 也可以从大到小扫描i, 如果每次anc[x][i]深度不小于y, 则跳x. 两种做法效果一样.
(3)求出LCA. 假设x与y向上走最小的L步后是同一结点, 也就意味着, x与y向上走最大的L-1步, 也是不同的结点. 可以从大到小枚举往上走2i步, 如果当前x与y向上走2i步后为同一点, 则停止, 否则一起向上走. 这样枚举停止后, x与y各向上走一步, 就是LCA

int de[maxn], anc[maxn][maxlog];
void dfs(int x, int fa) //初始化de数组与anc数组
{
de[x] = de[fa] + 1;
anc[x][0] = fa;
for(int i = 1; i < maxlog; i++) anc[x][i] = anc[anc[x][i-1]][i-1];
for(int i = fi[x]; i; i = ne[i])
if(to[i] != fa)
dfs(t[i], x);
}
int getlca(int x, int y)
{
if(de[x] < de[y]) swap(x, y);
for(int i = maxlog-1; ~i; --i) //等价i>=0
if(de[anc[x][i]] >= de[y])
x = anc[x][i]; //跳到深度一样
if(x == y) return x; //y是x的祖先
for(int i = maxlog-1; ~i; --i)
if(anc[x][i] != anc[y][i]) //完成祖先的枚举
x = anc[x][i], y = anc[y][i];
return anc[x][0];
}

c:转化为RMQ问题

没有看懂

d:塔扬离线算法

适用范围比较小,时间复杂度最优

6:最小生成树

有两个算法一个属Kruskal算法,一个是Prim算法

这两个是下周学习的重点,下周争取学会这两个

目前这两个算法我都没怎么看明白

[NOIP2013 提高组] 货车运输 - 洛谷

二:搜索

这周通过对图论的学习,感觉搜索和图论的关系密切,搜索是其他算法的基石。

本周在做题的过程中,遇到了很多问题,很多题都是能过测试点,但是提交一片红。

比如:b拯救oibh总部 - 洛谷

需要给地图外加上虚拟边框才行

1:收获:

目前做题速度非常的慢,差不多一个小时才能A掉一道题,虽然理论都明白,但在实际做题过程中发现各种问题层出不穷

a:笔算

我发现笔算非常重要,在我有问题无法解决的时候,我就去把我写的代码打印出来,还有题解代码都打印出来,仔细去研究,每一步的执行结果,比仅凭想象好很多。

b:看头文件源码

有些题在某个测试点WA不出来,时去看头文件源码,仔细分析头文件源码,会大有收获,比如gets读到EOF会返回nall如果while(gets(str)!=EOF)就会出问题。

c:洛谷的讨论区非常有用

很多时候自己的问题在讨论区都有。

2:感受

独立思考,勇于尝试,非常重要。不要怕错,只有在不断地调试BUG过程中才会有提高,那一片绿中的一个WA正是应当学习的点。搜索要多做题练手,否则思虑有写不出来!