- 洛谷题单指南-图的基本应用-P2853 [USACO06DEC] Cow Picnic S
原题链接：https://www.luogu.com.cn/problem/P2853题意解读：找到所有奶牛都可以到达的牧场，就是要从奶牛所在位置开始遍历，求所有奶牛能重合的点的个数。解题思路：直接从从牛奶所在位置进行DFS，记录每个位置有奶牛能到的个数，个数等于奶牛总数的即合适的牧场。100分代码：#include<bi......
- 洛谷题单指南-图的基本应用-P1127 词链
原题链接：https://www.luogu.com.cn/problem/P1127题意解读：按字典序排列单词，使得相邻单词的首位字母一样。解题思路：由于单词之间可以相邻的条件是前一个单词的末尾字母和后一个单词的开头字母一样，因此可以遍历每一个单词，再找到每一个可以接在其后面的单词，建立一个邻接表，然后从......
- python之类8.1
一、介绍类类(class):用来描述具有相同的属性和方法的对象的集合。它定义了该集合中每个对象所共有的属性和方法。对象是类的实例实例化：创建一个类的实例，类的具体对象。对象：通过类定义的数据结构实例。对象包括两个数据成员（类变量和实例变量）和方法方法：类中定义的函数类变......
- 洛谷题单指南-图的基本应用-P1807 最长路
原题链接：https://www.luogu.com.cn/problem/P1807题意解读：由于对于每一条边u->v，都有u<v，因此节点1的入度一定是0，且是有向无环图，直观上可以通过拓扑排序法搜索每一个节点，计算1到每一个节点的最长距离。但问题在于，入度为0的节点可能不止一个，这样在计算到某个点的最长距离时，会受到......
- 洛谷题单指南-图的基本应用-P4017 最大食物链计数
原题链接：https://www.luogu.com.cn/problem/P4017题意解读：食物链的顶端不会被其他生物吃，在图结构中设定为入度是0，食物链的底端不会吃其他生物，在图结构式设定为出度是0，此题就是要计算所有入度是0的点到所有出度是0的点一共有多条路径。解题思路：首先，来模拟一样样例，样例数据形成的......
- 洛谷题单指南-图的基本应用-P3916 图的遍历
原题链接：https://www.luogu.com.cn/problem/P3916题意解读：寻找每个点所能到达的最大的点。解题思路：直观上，可以依次从每个点开始DFS搜索，记录经过的最大点，复杂度是O(n^2)级别，会超时。可以换一种角度，既然要找每个点可以达到的最大值，那么可以反向建图，从最大值出发，所经过的点能达到......
- 洛谷题单指南-图的基本应用-P5318 【深基18.例3】查找文献
原题链接：https://www.luogu.com.cn/problem/P5318题意解读：图的建立、DFS、BFS模版题。解题思路：本题主要考察建图、图的DFS、BFS遍历。建图方式：领接表vector<int>g[N];需要注意的是，在DFS、BFS搜索领接点时，需要先将领接点编号排序，满足题目要求的“如果有很多篇文章可以参阅，请......
- 洛谷题单指南-集合-P2814 家谱
原题链接：https://www.luogu.com.cn/problem/P2814题意解读：已知多组父子关系，找某个人最早的祖先，并查集的应用。解题思路：由于存在真正的父子关系，所以在并查集合并的时候，要把p[x]=y中x设置为子，y设置为父，其余都是并查集的常规操作。由于是计算姓名之间的父子关系，并查集可以用map......
- 洛谷题单指南-集合-P3879 [TJOI2010] 阅读理解
原题链接：https://www.luogu.com.cn/problem/P3879题意解读：此题本质上是计算倒排索引，所谓倒排索引，即不是通过文章来找单词，而是通过单词来找文章。解题思路：要建立单词和文章之间的关系，一个单词对应多篇文章，且要按照文章编号排序，可以使用如下数据结构：map<string,set<int>>h;只......
- 洛谷题单指南-集合-P1955 [NOI2015] 程序自动分析
原题链接：https://www.luogu.com.cn/problem/P1955题意解读：要判断约数条件是否可以同时满足，主要是要判断不相等的情况。解题思路：对于相等的条件，直接进行集合合并即可；对于不相等的条件，判断两者是否属于同一个集合，如果形成矛盾，则条件不能成立。由于i，j的范围至10^9，定义并查集如果......