大大大芒果

分类

图论(16) 学习笔记(11) 数学知识(3) 赛后总结(15)

/ 注册

全部文章（共46篇）

求最近公共祖先的三种方法（LCA）

书P375~380以下规定：n为树的点数，m为询问次数http://acm.hdu.edu.cn/showproblem.php?pid=2586luogu模版题：https://www.luogu.com.cn/problem/P3379 注意，多组数据一定要把所有变量清空！！！ ①向上标记法时间...

2020-10-18

1 558

求树的直径的两种算法

书P369~371①：树形DPhttps://www.cnblogs.com/kma093/p/9742317.html #include<bits/stdc++.h> using namespace std; const int maxn=2e6+10; const double ep...

2020-10-18

0 528

POJ2728 最优比率生成树

书P368题目地址：https://ac.nowcoder.com/acm/contest/1056/C ① 0/1分数规划https://blog.nowcoder.net/n/70ad985a57bc4085aaee4d40fd2a9451 ② Prim算法https://blog.nowcod...

2020-10-16

0 701

0/1分数规划

书P185 0/1分数规划是指给定n对整数ai和bi，从中选若干对，使选出的数对的a之和与b之和的商最大猜测一个值L，然后考虑是否存在一组解{x1,x2,...,xn}，满足：如果：则L比答案小，否则比答案大因为L具有单调性，所以可以使用二分法。模版题：POJ2976 更详细地介绍：htt...

2020-10-15

0 885

POJ1639 Picnic Planning

题目链接：https://ac.nowcoder.com/acm/contest/1056/B书P368 ①：Kruskal算法https://blog.nowcoder.net/n/012b92baab1f4ee59bb17b9bcb8dadb4本题中用这个算法求去掉根节点1后的最小生成树 ②贪心...

2020-10-15

0 579

CH6201 走廊泼水节

题目地址：https://ac.nowcoder.com/acm/contest/1056/A思路：n个节点的树有n条边，先把边从小到大排序，依次扫描每一条边。如果是一条边，那么就不需要加边如果是二条边，需要加一条边，这条边的权值应该是当前边的权值+1，如果加边的权值相同，最小生成树就不唯一如果是三...

2020-10-12

0 513

最小生成树

①Kuskal算法（克鲁斯卡尔）时间复杂度为O(m log m) #include<bits/stdc++.h> using namespace std; const int maxn=2e5+10; struct edge { int u,v,w; }; edge a[maxn];...

2020-10-12

1 584

矩阵乘法

书P156设 A 是 n * m 矩阵，B 是 m * p 矩阵，则 C = A * B 是 n * p 矩阵则：即 C 第 i 行第 j 列数，是由 A 的第 i 行的 m 个数与 B 的第 j 列的 m 个数分别相乘再相加得到的得到的是一个 n * p 的矩阵矩阵乘法满足结合律，分配律...

2020-10-12

0 463

从点S到E刚好经过N条边的最短路径

题目地址：https://ac.nowcoder.com/acm/contest/1055/G《算法进阶》P362 ①关于min的矩阵乘法：https://blog.nowcoder.net/n/09c63cb41aba4ab5bf67450b243e0eba若矩阵保存任意两点之间恰好经过m条边的...

2020-10-12

0 451

用floyd找最小环

#include<bits/stdc++.h> using namespace std; const int INF=0x3f3f3f3f; const int maxn=300+10; int a[maxn][maxn],d[maxn][maxn],pos[maxn][maxn];//...

2020-10-12

1 470