大大大芒果

图论

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

/ 注册

全部文章 / 图论（共16篇）

二分图最大匹配

参考：https://www.luogu.com.cn/blog/fusu2333/post-2018-wu-yi-qing-bei-pei-xun-er-fen-tu-xiong-ya-li-suan-fa-post 模板：https://www.luogu.com.cn/problem/P338...

2021-08-04

0 465

有向图的必经点和边

书P417 例题：https://ac.nowcoder.com/acm/contest/1061/C #include<bits/stdc++.h> #define x first #define y second using namespace std; const int N = ...

2020-10-28

0 770

强连通分量/缩点（POJ1236）

洛谷P2002 书P416 例题：https://ac.nowcoder.com/acm/contest/1061/A #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define maxn 1...

2020-10-28

1 656

求欧拉回路

书P409 #include <bits/stdc++.h> using namespace std; const int SIZE=100010; int head[SIZE],ver[SIZE],Next[SIZE],tot; int Stack[SIZE*10],ans[SIZE*...

2020-10-27

0 621

无向图双连通分量与缩点相关概念

书P401 需要具备的知识：①：tarjan求割点与割边：https://blog.nowcoder.net/n/dc5fbd4588164fb4b37847a11ea7f499 若一张无向图不存在割点，则为点双连通图。若一张无向图不存在割边（桥），则为边双连通图。无向图的极大点双连通子图为点双连...

2020-10-26

0 622

无向图的Tarjan算法（割边与割点）

书P394~399 1、割边判定模版题:P1656 https://www.luogu.com.cn/problem/P1656 #include <bits/stdc++.h> using namespace std; const int SIZE=100010; int head[S...

2020-10-26

0 701

POJ3417 闇の连锁

书P380 ① LCA:https://blog.nowcoder.net/n/cbc02f19ffa7450d9298b9474c6bd4b8 ② dfs:https://blog.nowcoder.net/n/abf5e27bb5c243ebb12d8aced6e11411 时间复杂度 O(n+...

2020-10-19

0 548

求最近公共祖先的三种方法（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 557

求树的直径的两种算法

书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 531

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 686