文章目录lcaTarjan板子题：1172.祖孙询问lca或tarjan：1171.距离356.次小生成树352.闇の連鎖lcaO(mlogn)O(mlogn)O(mlogn)，n为节点数量，m为询问次数，lca是一种在线处理询问的算法自己也是自己的祖先倍增：fa(i,j)fa(i,j)fa(i,j)表示从i开始，向上走2j2^j2j步走到的点j=0，走到父节点j>0，分两步走，先走到2j−12^{j-1}2j−1步再走2j−12^{j-1}2j−1步，那么一共就会走2j2^j2j步，fa(i,j)=fa(fa(i,j−1),j−1)fa(i,j)=fa(fa(i,j-1),j-1)fa(i,

文章目录裸题：904.虫洞01分数规划：361.观光奶牛特殊建图与01分数规划+trick：1165.单词环裸题：904.虫洞904.虫洞-AcWing题库//虫洞是负权且单向边，道路是正权且双向边，题目较裸，判断有无负环即可#include#includeusingnamespacestd;constintN=510,M=6010;inth[N],e[M],ne[M],w[M],idx;intn,m,k;intdis[N],cnt[N];intq[N];boolst[N];voidadd(intx,inty,intd){e[idx]=y,ne[idx]=h[x],w[idx]=d,h[x]=

主要涉及链式前向星，dijkstra算法，Floyd算法，及其相应摸版。目录第一题:查找文献思路：代码：第二题：Floyd思路：代码： 第三题：单源最短路径思路：代码：第一题:查找文献P5318【深基18.例3】查找文献-洛谷|计算机科学教育新生态(luogu.com.cn) 思路：这个主要考察单边遍历问题，涉及到BFS和DFS的利用，可以采用vector存图来简化空间复杂度，同时注意记得排序。代码：#includeusingnamespacestd;constintM=1e6+5;vectorf[M];queueQ;boolvis[M];//全局变量一开始全部为0voiddfs(intx){

目录〇，全文说明、宏定义代码一，单例、快速幂、数论二，并查集、DancingLink、无向图、最小生成树三，有向图、单源最短路径、连通分量四，网格图、回路链路、路径重建五，test〇，全文说明、宏定义代码类里面和宏定义处都有接口注释，因为宏不体现具体参数，所以注释以类里面的为准。除了并查集和DancingLink被其他类使用之外，其他所有的代码依赖关系都只体现在类的继承关系中。所有代码放在一起是可以编译运行的，如果按照章来划分，除了最后一章是测试代码，其他任意一章都可以单独编译运行。宏定义代码：///（1.1）单例/////SingleA略。单例模板///（1.2）快速乘法、幂、矩阵幂////

毕克定理是小学四年级奥赛内容，无意间从一本教材上看到，觉得定理蛮有意思，也和自己从事的工作有一些关联，就在网上找了一些证明资料，结合自己的思考，稍微挖掘了以下，聊以记录。毕克定理是指一个计算点阵中顶点在格点上的多边形面积公式，该公式可以表示为S=N+L÷2－1，其中N表示多边形内部的点数，L表示多边形落在格点边界上的点数，S表示多边形的面积。公式默认一个小正方形边长为1，即面积为1，若一个格点正方形边长为2（面积为4）时，需要在原有公式的基础上乘4.1.定理大概描述：给定一个网格，每个格子由边长为1的单位正方形组成。网格内有一个多边形，并且多边形的顶点都在网格的交点处，也就是说顶点没有一个落在

文章目录1137.选择最佳线路1131.拯救大兵瑞恩1134.最短路计数383.观光dp是特殊的最短路，是无环图（拓扑图）上的最短路问题1137.选择最佳线路1137.选择最佳线路-AcWing题库//反向建图就行#include#include#includeusingnamespacestd;typedefpairint,int>PII;constintN=1e3+10,M=2e4+10;inth[N],e[M],ne[M],w[M],idx;intn,m,s;inta[N];intdis[N];boolst[N];voidadd(intx,inty,intd){e[idx]=y,ne[i

一、DFS与BFS1.1深度优先搜索(DFS)DFS不具有最短性//排列数字问题#includeusingnamespacestd;constintN=10;intn;intpath[N];boolst[N];voiddfs(intu){if(u==n){for(inti=0;i>n;dfs(0);return0;}1.2宽度优先搜索(BFS)一层一层搜索，可以搜到最短路。  //走迷宫问题#include#include#include#includeusingnamespacestd;typedefpairPII;constintN=110;intn,m;intg[N][N];intd[N

图论提高最小生成树（1）朴素版prim算法（O(n2)O(n^2)O(n2)）适用范围：稠密图易错：注意有向图还是无向图；注意有没有重边和负权边。从一个集合向外一个一个扩展，最开始只有111这个结点，然后把元素一个一个加进来，每次加的元素就是离这个集合距离最小的元素，可以设为jjj。每次加进来后，就更新其他点到这个集合的距离，更新的数值就是其他点到jjj的边的长度。intg[maxn][maxn],d[maxn],N,M;boolvis[maxn];intprim(){ intres=0; for(inti=1;iN;i++)d[i]=INF; for(inti=0;iN;i++){ int

文章目录841.钥匙和房间DFSBFS127.单词接龙684.冗余连接685.冗余连接II657.机器人能否返回原点31.下一个排列463.岛屿的周长解法1解法21356.根据数字二进制下1的数目排序解法1解法2注意点图论：题841、127并查集：题684、685模拟：题657、31、463位运算：题1356841.钥匙和房间分析：这道题是有向图，图1的所有节点都是连接的，而图二中的节点2是孤立的，不能进入所有房间。孤立问题可以用并查集的方式去解决，但本题是有向图。图2中，0号房间拿到1、3号房间的钥匙，可以去1、3号房间；1号房间拿到0、1、3号房间的钥匙，可以去0、1、3号房间；2号房间只

Problem-E-Codeforces题意：思路：注意到题目的性质：满足条件的路径个数是极少的，因为每个点离路径的距离先考虑一条链，那么直接就选最深那个点作为端点即可为什么，因为我们需要遍历所有点的父亲推广到树，也是要遍历所有点的父亲为什么要加枚举的tag，因为可以发现满足条件的链的状态数很少，可以把这个作为切入点Code：#include#defineintlonglongusingnamespacestd;constintmxn=2e5+10;constintmod=1e9+7;vectorG[mxn];intN,M,K,u,v,x;intidx=0;intdep[mxn],In[mxn