个人技术分享

发现之前做的题很乱，用小笔记把看过的博客和题目分类记录一下，代码参考了很多佬，是标注出来的链接，若不同意我就删掉（鞠躬）找了几张好点的，图来源图中的id和acwing。

【刷题（12）】图论

竞赛常用知识之图论2（最小环，最小生成树）

发现之前做的题很乱，用小笔记把看过的博客和题目分类记录一下，代码参考了很多佬，是标注出来的链接，若不同意我就删掉（鞠躬）找了几张好点的，图来源图中的id和acwing。

生成树的计数还可以通过计算Laplace矩阵任意元素的代数余子式求得。G-e的k着色方案可以分为两类：e的两个端点着不同色的为。G的生成树的颗数，可以分为两类：包含边e的为。， e的两个端点着相同色的为。

HDU2196Computer（树形dp）给出一个n个节点的无根树，求每个节点所能到达的最远距离。

数据水，不用判>INF/2。

发现之前做的题很乱，用小笔记把看过的博客和题目分类记录一下，代码参考了很多佬，是标注出来的链接，若不同意我就删掉（鞠躬）找了几张好点的，图来源图中的id和acwing。

我们想，既然我们已经到了第i个水果了，证明说前面的水果我们都已经挑选完毕了，我们可以枚举前面j个水果（j=i来表示。既然不买，那么肯定就必须是前面买过的水果里有覆盖这个水果的。dp[i][1]=min(dp[i-1][0],dp[i-1][1])+prices[i-1]（这里i是从2开始的）dp[i][1]表示的就是选择买第i个水果，另外一个状态就是不买了。dp[i][0]=min(dp[i][0],dp[j][1])这就是不选择买当前水果的方程。

对于图G=（V，E）有两种表示方法：邻接链表和邻接矩阵，两种表示方法既可以表示有向图，也可以表示无向图。如果 G 是连通图，则，一个图连通，至少有 v -1 条边。，而，此外要判断两个节点之间是否有边相邻，可以快速通过邻接矩阵判断。

初始化邻接矩阵（有边直接连接的直接存，没有的存INF最大值，自己到自己的路径长度为0）遍历（k，i，j）更新i到j的最短路，通过k依据题意更新答案。

P3386 【模板】二分图最大匹配P1525 [NOIP2010 提高组] 关押罪犯P3385 【模板】负环P3371 【模板】单源最短路径（弱化版）SPFADij：P3385 【模板】负环P5960 【模板】差分约束

25考研知识点个人向总结。

P3386 【模板】二分图最大匹配P1525 [NOIP2010 提高组] 关押罪犯P3385 【模板】负环P3371 【模板】单源最短路径（弱化版）SPFADij：P3385 【模板】负环P5960 【模板】差分约束

手痒想写代码........2024年5月6日——5月13日。

以上简单介绍了，图论知识。对于图论中用的比较多最短路和k短路用Java实现了。实际图论是比较难的问题，这边只是做了简单的介绍，抛砖引玉。

【代码】图论专题训练。

差分约束的图论解决方法

LeetCode刷题笔记之图论

图由顶点和边组成，所以我们在表示一个图的时候，使用GVEG=(V,E)GVE，来表示一个G图，其中的V表示G图中的顶点，E表示G图中的边；对于G图中顶点和边的表示就是采用集合的形式来表示，Vv1v2v3⋅⋅⋅⋅Vv1​v2​v3​⋅⋅⋅⋅，同样的对于边E也可以采用集合来表示出来；同时图的顶点集不可以为空，图的边集可以为空，每一条线都要连接两个节点。