ACM图论模板_BY夏天的风资源-CSDN文库

夏天的风

5星 · 超过95%的资源需积分: 12 160 浏览量 2014-08-10 11:51:11 上传评论 3 收藏 1.15MB PDF 举报

资源推荐

资源详情

资源评论

ACM Standard Code Library

夏天的风

Hangzhou Dianzi University

Ver 2.0

Update 2014/04/11

图论

并查集................................................................................................................................................. 9

模板............................................................................................................................................. 9

种类并查集(分层).............................................................................................................. 9

并查集应用.................................................................................................................................9

逆向并查集.........................................................................................................................9

最小生成树.......................................................................................................................................10

模板........................................................................................................................................... 10

Kruskal: 并查集+排序.....................................................................................................10

Prim (n^2).......................................................................................................................10

最小树形图(有向图的最小生成树)[hdu2121]...............................................................10

K 度限制生成树................................................................................................................12

最小比率生成树...............................................................................................................15

斯坦纳树...........................................................................................................................16

最小生成树应用.......................................................................................................................17

寻找 MST 每条边的最佳替换边[hdu4126]................................................................... 17

LCA && RMQ................................................................................................................................ 19

模板........................................................................................................................................... 20

LCA 朴素法......................................................................................................................20

LCA 倍增法......................................................................................................................20

一维 RMQ.........................................................................................................................22

二维 RMQ.........................................................................................................................23

LCA && RMQ 应用.................................................................................................................25

一维 RMQ 查找最大值下标........................................................................................... 25

树上删一条边,M 条边中也删一条边[POJ3417]........................................................... 25

最短路............................................................................................................................................... 27

模板........................................................................................................................................... 27

Dijkstra+优先队列 O(E*logE)........................................................................................27

SPFA+连接表 O(kE)....................................................................................................... 27

Floyd O(n^3)..................................................................................................................... 28

最短路的应用...........................................................................................................................29

带限制最短路...................................................................................................................29

对偶图(平面最小割)........................................................................................................ 29

最小路径树+删边最短路................................................................................................ 29

第 K 短路(A*).................................................................................................................. 31

最短路和次短路条数.......................................................................................................32

经过 N 条边的最短路......................................................................................................33

最优比率环.......................................................................................................................34

最短路+记忆化搜索........................................................................................................ 35

⒀有保护节点的最短路[hdu3873]..................................................................................37

经过某些点,回到原点的最短路(状压 DP).....................................................................39

Bellman 寻找负权回路的点............................................................................................ 39

双调旅行商问题...............................................................................................................40

最小环条数.......................................................................................................................41

差分约束系统...................................................................................................................42

二分匹配...........................................................................................................................................43

模板........................................................................................................................................... 43

二分匹配(连接表)[一对一]............................................................................................. 43

多重匹配(连接矩阵)[多对一]......................................................................................... 44

HK 匹配算法.................................................................................................................... 45

二分匹配的应用.......................................................................................................................46

奇偶分图匹配...................................................................................................................46

最小点覆盖(最大独立集)................................................................................................46

最小路径覆盖...................................................................................................................46

二分+多重匹配[hdu1669]................................................................................................46

输出匹配情况(字典序最大最小)....................................................................................47

二分匹配必须边...............................................................................................................47

二分匹配关键点[hdu1281]..............................................................................................47

二分匹配好题[BNU14507]..............................................................................................47

关键点&&必须边.............................................................................................................48

一般图的最大匹配(带花树)............................................................................................................51

模板........................................................................................................................................... 51

可搞定一类棋盘博弈问题[zoj3316]...............................................................................51

一般图最大匹配的应用...........................................................................................................53

棋盘取棋子博弈[zoj3316]............................................................................................... 53

棋盘移动 king 博弈[hdu3446].........................................................................................54

KM 匹配........................................................................................................................................... 54

模板........................................................................................................................................... 54

最小权匹配.......................................................................................................................54

套模板注意事项...............................................................................................................56

KM 匹配的应用....................................................................................................................... 56

边权之积最大...................................................................................................................56

收益最大,且边的改动最少(1).........................................................................................56

收益最大,且边的改动最少(2).........................................................................................57

其他类型...........................................................................................................................58

[招聘员工]........................................................................................................................ 59

[货物运输]........................................................................................................................ 59

[最短匹配]........................................................................................................................ 59

[工作分配]........................................................................................................................ 59

一般图的最小权匹配.......................................................................................................................60

模板........................................................................................................................................... 60

一般图的最小权匹配的应用...................................................................................................62

无向图中国邮路问题.......................................................................................................62

输出最小权值的回路.......................................................................................................62

最大团&&稳定婚姻........................................................................................................................ 62

模板........................................................................................................................................... 62

最大团...............................................................................................................................63

稳定婚姻匹配(白爷模板)................................................................................................63

最大团&&稳定婚姻的应用.................................................................................................... 65

最大独立集[poj1419].......................................................................................................65

二分+最大团.....................................................................................................................66

计算极大团个数...............................................................................................................66

着色问题(四色定理)[最大团的应用]............................................................................. 67

强连通&&双连通............................................................................................................................ 67

模板........................................................................................................................................... 67

强连通...............................................................................................................................68

边双连通...........................................................................................................................69

点双连通...........................................................................................................................70

强连通&&双连通的应用.........................................................................................................72

强连通初步.......................................................................................................................72

受欢迎的牛(只有 1 个度数为 0).....................................................................................73

强连通缩点+树形 dp(累加子节点的总权值)................................................................ 73

缩点+拓扑.........................................................................................................................73

仙人掌图...........................................................................................................................73

[双连通寻找奇圈]............................................................................................................ 74

[混合图改有向图]............................................................................................................ 75

[最少支撑点].................................................................................................................... 77

[LOW 和 DFN 的应用]....................................................................................................77

[强连通总结].................................................................................................................... 79

[双连通总结].................................................................................................................... 80

2-SAT................................................................................................................................................ 81

2-SAT 的应用........................................................................................................................... 82

题目分析...........................................................................................................................82

二分+2-SAT...................................................................................................................... 83

2-Sat 输出路径................................................................................................................. 83

输出字典序最小(只能爆搜)............................................................................................85

欧拉回路...........................................................................................................................................87

模板........................................................................................................................................... 87

欧拉回路的应用.......................................................................................................................89

每条边来回进过两次.......................................................................................................89

磁鼓欧拉回路...................................................................................................................89

00-99 连接成最短串........................................................................................................ 90

混合欧拉回路...................................................................................................................91

竞赛图............................................................................................................................................... 93

竞赛图的应用...........................................................................................................................94

找三元环...........................................................................................................................94

输出哈密顿路...................................................................................................................94

输出哈密顿回路...............................................................................................................96

[构造哈密顿路,每个点度 d(v)>=(n+1)/2].....................................................................100

拓扑排序.........................................................................................................................................101

模板......................................................................................................................................... 101

拓扑排序的应用.....................................................................................................................101

拓扑判环.........................................................................................................................101

三维拓扑排序.................................................................................................................102

[执行任务]...................................................................................................................... 103

网络流............................................................................................................................................. 104

模板......................................................................................................................................... 104

EK(连接表).....................................................................................................................104

SAP(连接表)...................................................................................................................105

费用流(连接表).............................................................................................................. 106

无向图最小割.................................................................................................................107

上下界网络流.................................................................................................................108

网络流建图总汇.....................................................................................................................110

点有权值,边没权值........................................................................................................110

二分图的点权覆盖于点权独立集.................................................................................111

点有权值,边也有权值(最大权闭包)............................................................................. 111

最小权的环覆盖整个图.................................................................................................111

[网络流关键割边][ZOJ2532].........................................................................................112

[网络流输出割边集]...................................................................................................... 112

[分层建图思想].............................................................................................................. 113

[费用相同的优先选一些点].......................................................................................... 113

[最大费用优先(可以不满流)]....................................................................................... 113

[最大权闭合子图].......................................................................................................... 113

[左上到右下走多次的最大价值](一个点的价值取了,第二次取的价值为 0)...........113

[选取区间问题][POJ3680],[POJ3762](工作安排)....................................................... 113

[按字典序输出割集]...................................................................................................... 113

[最小点权覆盖][POJ3308][行列覆盖]..........................................................................114

[项目最小花费问题][最小割]....................................................................................... 114

[无向图判断边割集是否唯一]......................................................................................114

[求有多少条边,减少 1 的流量,最大流减少?]RQNOJ 石油运输................................115

[输出边不相交的两条最短路径][SGU185]................................................................. 115

[混合欧拉定向, 输出路径][UVA10735] Euler Circuit................................................ 115

网络流的应用.........................................................................................................................115

来回不重复最短路.........................................................................................................115

二分+网络流(挤奶,floyd+最大流+二分)......................................................................115

最小点权覆盖+输出割点(Destroying The Graph)........................................................116

最大密度子图+输出子图...............................................................................................117

无向图全局最小割.........................................................................................................119

01 规划+输边割集..........................................................................................................119

求最小点割集(最大点权独立集)..................................................................................120

数和思想(行进列出)...................................................................................................... 120

剩余203页未读，继续阅读

评论收藏

内容反馈

J_Sure

2014-09-13

真是清晰全面，膜拜+仰慕 Orz
BigBallon

2016-07-21

相当好的模板，风神V5
lemonoil

2017-10-12

还可以，大家看看吧
Joker_Zgh

2017-02-26

包含很多东西了这个，见过的没见过的都有
二手的玫瑰

2015-03-06

风神的好东西

夏天的风

粉丝: 490
资源: 2

ACM图论模板_BY夏天的风

ACM图论模板合集.pdf

最好最全的ACM模板

ACM图论数据结构常见模板

浙江大学ACM模板(经典代码）.pdf

ACM新手总结的部分图论模板

对参加ACM竞赛非常有用的几个ACM关于图论的答题模板

所有ACM所需要的基本算法模板（图论，数论，计算几何，位运算，组合数学等）

浙江大学ACM模板 计算几何，图论，数据结构，经典题的模板

ACM算法模板集锦（几何，结构，其他，数论，数值计算，图论）

上海交大ACM模板_上海交大ACM模板_ACM模板_

acm.zip_acm图论_acm图论学习

ACM模板-f_zyj.zip_ACM模板_ACM模板-f_zyj_CSDN积分_acm必备模板_f_zyj ACM

kuangbin的ACM模板（新）_ACM模板_ACM算法总结_

ACM模板代码图论数论数据结构STL

山东大学ACM模板-图论

ACM专用模板，包括数据结构，图论，字符串，数论，几何计算，KD树，ST表，二叉搜索树，二维ST表（任意矩形，正方形），二维树状数组模板，分块ACM模板.rar

acm模板_acm模板

ACM-SJTU.rar_ACM_SJTU ACM模板_acm.sjtu_sjtu_sjtu hao yuan acm

ACM函数整理_ACM模板

ACM模板(浙大)_算法竞赛_ACM模板_ACM_源码

acm函数整理_模板

D:\acm\ACM函数整理_ACM模板.pdf

浙江大学ACM题解JU_ACM_All_Anwer

Acm自制模板_zwz_v2.1.pdf

ACM 图论知识大全

ACM.zip_ACM算法_solvea78_算法_算法模板_算法模版

hdu_ACM.rar_ACM_hdu_hdu acm_hdu_ACM_杭电ACM

acm模板_ACM_

ACM模板ACM 模板

最新资源

浙江大学ACM模板计算几何，图论，数据结构，经典题的模板