这是一道图论题：

题面：

图G是一个无向连通图，没有自环，并且两点之间至多只有一条边。我们定义顶点v,u最短路径就是从v到u经过边最少的路径。所有包含在v-u的最短路径上的顶点被称为v-u的Geodetic顶点，这些顶点的集合记作I(v, u)。
我们称集合I(v, u)为一个Geodetic集合。
例如下图中，I(2, 5)={2, 3, 4, 5}，I(1, 5)={1, 3, 5}，I(2, 4)={2, 4}。

给定一个图G和若干点对v,u，请你分别求出I(v, u)。

分数 30！

可以说这次打的是挺不甘的，这次犯了几个严重的错误，先列一下。

• 没吃饭就来了（很影响思考的…）
• 做题顺序不对

这次做题由于没吃饭，感觉整个人都很蒙… 先看了下
t1，可以说这次败笔就在t1，（评测完之后，用了不到10分钟给A掉了，发现这道题很水，同时感觉自己好傻…），由于做完上周的一套题，t1求有向图的强连通分量，虽然是裸tarjan，但是也是比较难的题了。于是我就提高了警惕…

有关于树这个数据结构，可以探讨的的东西有很多，但这篇博客是有关于树结构的一些代码模板，进行一下总结。

无根树转有根树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//有根树转无根树
vector<int> G[MAXN];	//用vector存图
inline void Read_Tree()
{
	int u,v;
	scanf("%d",&n);
	for (int i=0;i < n-1; i++)
	{
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
}

inline void dfs(int u,int fa)	//转换为以 u 为根的子树，u 的父节点为fa
{
	int d = G[u].size();
	for (int i = 0; i < d; i++)
	{
		int v = G[u][i];
		if (v != fa)	dfs(v, p[v] = u);
	}
}

今天来总结一下图论的欧拉路问题

我们一般把一个图中点的入度和出度的和为偶数的点叫做偶点，反之叫做奇点。关于欧拉图有以下定义（在连通图中适用）

1. 凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。
2.凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点终点。
3.其他情况的图都不能一笔画出。（奇点数除以二便可算出此图需几笔画成。）

根据以上定义，我们可以判断一个图至少需要几笔可以画完。

落谷上也有道题关于判断欧拉路的基本练习

P1636 欧拉路基本练习

这篇主要总结一下图论有关的代码模板；
主要由以下几个部分：

• 图的建立和读入

• 图的遍历

  • DFS
    • BFS

• 图的最短路问题

  • Floyd 算法（多源最短路可带负环）（可求图的连通性）O(n*n*n)
    • Dijstra 算法（单源最短路径不可带负环）（可进行堆优化） O(n*n)
    • Bellman-ford 算法（单源最短路可判负环）O(n*m)
    • SPFA 算法 （单源最短路可判断负环）O(n*m)

• 图的最小生成树问题(MST)

  • kruskal 算法
    • Prim 算法

今天来抽空来学习一下 Google 的 C++ 代码规范，有关于这个规范的文件来自于下面这个网址

参考链接：

Google C++ Code Style

C++ 参考手册

从第一个网站里面学到了一些对自己代码格式等方面规范有帮助的东西，所以来总结一下，同时这个网站里的内容很多，有大量些项目的指导，由于水平有限就只摘了我认为有用的一部分内容。

有关于数据结构的知识也接触的不少了,今天来总结一下并查集

并查集如同其名字一般,主要功能就是”并”和”查”,用来处理一些不相交集合的合并 及查询问题。
该数据结构的主要优势在于在数据量极大的情况下,能将时间复杂度保持在一个可以接受的水平之内。如果用正常的数据结构来描述的话,往往会出现空间及时间复杂度过高的情况。

由于并查集的主要操作有两种,合并和寻找,为了提高效率,我们往往在寻找的过程中使用路径压缩来保证下次查找的时候速度更快。

在竞赛中，遇到大数据时，往往读文件成了程序运行速度的瓶颈，需要更快的读取方式。

常用的读入一般为 scanf 读入和 cin 读入两种,相比之下 scanf 的读入效率要高于 cin 。对于这种情况我们常常会关闭 cin 的同步来提高 cin 的效率

1

std::ios::sync_with_stdio(false);

但是在一些情况下,我们一般使用快速读入来读入数据,以保证在大规模数据需要读入的情况下来节约更多的时间.

Where there is darkness， may we bring light
Where there is despair, may we bring hope
Where there is doubt, may we bring faith
Where there is hatred, may we bring love

Good morning, and in case I don’t see you,
Good adernoon. Good evening. And good night.

How is it going to end？

研究物理的人如果遇到不理解的事情，总是可以责怪上帝，世界这么复杂不是你的错。但是如果你的程序有问题，那就找不到替罪羊了。0就是0，1就是1，就是你把它搞砸了。

软件测试可以确定软件里有 bug，但却不可能用来确定它们没有 bug。

日拱一卒 功不唐捐

有志者，事竟成，破釜沉舟，百二秦关终属楚； 苦心人，天不负，卧薪尝胆，三千越甲可吞吴！

我们都是被嫌弃的人、被讨厌的人、不被喜欢的人。如果不介意自己被嫌弃，反而一直努力的话，到最后反倒会变成受人喜爱的人。

所谓考试就是站在一些奇奇怪怪的角度，去看你在路上走了多远，但事实上你走了多远，欣赏到多少美丽的沿途的风景，也只有自己知道了。