-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathvol2.aux
242 lines (242 loc) · 21.8 KB
/
vol2.aux
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
\relax
\providecommand\HyperFirstAtBeginDocument{\AtBeginDocument}
\HyperFirstAtBeginDocument{\ifx\hyper@anchor\@undefined
\global\let\oldcontentsline\contentsline
\gdef\contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
\global\let\oldnewlabel\newlabel
\gdef\newlabel#1#2{\newlabelxx{#1}#2}
\gdef\newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
\AtEndDocument{\ifx\hyper@anchor\@undefined
\let\contentsline\oldcontentsline
\let\newlabel\oldnewlabel
\fi}
\fi}
\global\let\hyper@last\relax
\gdef\HyperFirstAtBeginDocument#1{#1}
\providecommand\HyField@AuxAddToFields[1]{}
\@writefile{toc}{\contentsline {part}{IV\hspace {1em}Algorithm}{7}{part.4}}
\@writefile{toc}{\contentsline {chapter}{\numberline {15}Graph Theory}{9}{chapter.15}}
\@writefile{lof}{\addvspace {10\p@ }}
\@writefile{lot}{\addvspace {10\p@ }}
\@writefile{toc}{\contentsline {section}{\numberline {15.1}Theorm}{9}{section.15.1}}
\@writefile{toc}{\contentsline {section}{\numberline {15.2}图数据结构}{9}{section.15.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.2.1}链式前向星}{9}{subsection.15.2.1}}
\@writefile{toc}{\contentsline {section}{\numberline {15.3}搜索}{10}{section.15.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.3.1}Dancing Links}{10}{subsection.15.3.1}}
\@writefile{toc}{\contentsline {subsubsection}{精确覆盖}{10}{subsection.15.3.1}}
\@writefile{toc}{\contentsline {paragraph}{精确覆盖}{10}{subsection.15.3.1}}
\@writefile{toc}{\contentsline {paragraph}{精确覆盖DLX模板}{10}{subsection.15.3.1}}
\@writefile{toc}{\contentsline {paragraph}{例：HUST 1017}{12}{subsection.15.3.1}}
\@writefile{toc}{\contentsline {subsubsection}{重复覆盖}{15}{subsection.15.3.1}}
\@writefile{toc}{\contentsline {paragraph}{重复覆盖}{15}{subsection.15.3.1}}
\@writefile{toc}{\contentsline {paragraph}{重复覆盖DLX模板}{15}{subsection.15.3.1}}
\@writefile{toc}{\contentsline {paragraph}{例：POJ 1084 Square Destroyer}{17}{subsection.15.3.1}}
\@writefile{toc}{\contentsline {subsubsection}{DLX标记已经提前选取过的列}{22}{subsection.15.3.1}}
\@writefile{toc}{\contentsline {section}{\numberline {15.4}基本图算法}{23}{section.15.4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.4.1}判断是否存在奇环、是否是二分图：交叉染色法($O(V+E)$)}{23}{subsection.15.4.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.4.2}2-SAT 问题($O(V+E)$)}{23}{subsection.15.4.2}}
\@writefile{toc}{\contentsline {subsubsection}{理论}{23}{subsection.15.4.2}}
\@writefile{toc}{\contentsline {paragraph}{建图}{23}{subsection.15.4.2}}
\@writefile{toc}{\contentsline {paragraph}{可行性判定}{24}{Item.9}}
\@writefile{toc}{\contentsline {paragraph}{构造解}{24}{Item.9}}
\@writefile{toc}{\contentsline {subsubsection}{实现}{24}{Item.9}}
\@writefile{toc}{\contentsline {paragraph}{Modified Edition of LRJ}{24}{Item.9}}
\@writefile{toc}{\contentsline {paragraph}{链式前向星写法}{27}{Item.9}}
\@writefile{toc}{\contentsline {paragraph}{按字典序排列结果的2-sat}{29}{Item.9}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.4.3}Euler 路径(未知复杂度)}{35}{subsection.15.4.3}}
\@writefile{toc}{\contentsline {subsubsection}{判定}{35}{subsection.15.4.3}}
\@writefile{toc}{\contentsline {paragraph}{无向图}{35}{subsection.15.4.3}}
\@writefile{toc}{\contentsline {paragraph}{有向图}{35}{subsection.15.4.3}}
\@writefile{toc}{\contentsline {paragraph}{混合图(有向+无向)}{35}{subsection.15.4.3}}
\@writefile{toc}{\contentsline {subsubsection}{有向图}{35}{Item.12}}
\@writefile{toc}{\contentsline {paragraph}{非递归}{35}{Item.12}}
\@writefile{toc}{\contentsline {paragraph}{递归(不建议用)}{36}{Item.12}}
\@writefile{toc}{\contentsline {subsubsection}{混合图(POJ 1637)}{37}{Item.12}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.4.4}Hamilton 回路}{41}{subsection.15.4.4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.4.5}弦图判断}{41}{subsection.15.4.5}}
\@writefile{toc}{\contentsline {section}{\numberline {15.5}无向图}{42}{section.15.5}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.5.1}割点($O(V+E)$)}{42}{subsection.15.5.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.5.2}割边(桥)($O(V+E)$)}{43}{subsection.15.5.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.5.3}双连通分量：Tarjan算法($O(V+E)$)}{45}{subsection.15.5.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.5.4}无向图的最小环($O(N^3)$)}{46}{subsection.15.5.4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.5.5}无向图最小割：Stoer-Wagner算法($O(N^3)$)}{47}{subsection.15.5.5}}
\@writefile{toc}{\contentsline {section}{\numberline {15.6}有向图}{49}{section.15.6}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.6.1}拓扑排序($O(V+E)$)}{49}{subsection.15.6.1}}
\@writefile{toc}{\contentsline {subsubsection}{高效版，默认字典序最小，可改最大}{49}{subsection.15.6.1}}
\@writefile{toc}{\contentsline {subsubsection}{输出所有序列}{50}{subsection.15.6.1}}
\@writefile{toc}{\contentsline {subsubsection}{其他版}{52}{subsection.15.6.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.6.2}强连通分量：Tarjan算法($O(V+E)$)}{53}{subsection.15.6.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.6.3}弱连通分量：Tarjan算法($O(V+E)$)}{55}{subsection.15.6.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.6.4}有向图的最小环($O(N^3)$)}{55}{subsection.15.6.4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.6.5}有向图最小权点基}{55}{subsection.15.6.5}}
\@writefile{toc}{\contentsline {section}{\numberline {15.7}树}{55}{section.15.7}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.7.1}树的直径}{55}{subsection.15.7.1}}
\@writefile{toc}{\contentsline {subsubsection}{权值为1的树的直径}{56}{subsection.15.7.1}}
\@writefile{toc}{\contentsline {subsubsection}{任意权值的树的直径}{56}{subsection.15.7.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.7.2}LCA \& RMQ}{57}{subsection.15.7.2}}
\@writefile{toc}{\contentsline {subsubsection}{dfs+ST在线算法}{57}{subsection.15.7.2}}
\@writefile{toc}{\contentsline {subsubsection}{LCA转化为RMQ的问题($O(N)$)}{60}{subsection.15.7.2}}
\@writefile{toc}{\contentsline {subsubsection}{离线Tarjan算法($O(N+Q)$)}{62}{subsection.15.7.2}}
\@writefile{toc}{\contentsline {subsubsection}{倍增算法，在线算法}{65}{subsection.15.7.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.7.3}最小斯坦纳树(Steiner Tree)($O(n3^k+cE2^k)$)}{68}{subsection.15.7.3}}
\@writefile{toc}{\contentsline {paragraph}{斯坦纳树(Steiner Tree)}{68}{subsection.15.7.3}}
\@writefile{toc}{\contentsline {paragraph}{最小斯坦纳树}{68}{subsection.15.7.3}}
\@writefile{toc}{\contentsline {paragraph}{最小斯坦纳树解法}{68}{subsection.15.7.3}}
\@writefile{toc}{\contentsline {paragraph}{模板}{68}{subsection.15.7.3}}
\@writefile{toc}{\contentsline {paragraph}{例：}{70}{subsection.15.7.3}}
\@writefile{toc}{\contentsline {section}{\numberline {15.8}最小生成树}{70}{section.15.8}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.8.1}Prim 算法($O(N^2)$)}{70}{subsection.15.8.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.8.2}Kruskal 算法(稀疏图)($O(E\qopname \relax o{lg}E)$)}{73}{subsection.15.8.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.8.3}增量最小生成树}{76}{subsection.15.8.3}}
\@writefile{toc}{\contentsline {paragraph}{增量最小生成树}{76}{subsection.15.8.3}}
\@writefile{toc}{\contentsline {paragraph}{算法1($O(NM\qopname \relax o{lg}N)$)}{76}{subsection.15.8.3}}
\@writefile{toc}{\contentsline {paragraph}{算法2($O(NM)$)}{76}{subsection.15.8.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.8.4}最小瓶颈路与最小瓶颈生成树}{76}{subsection.15.8.4}}
\@writefile{toc}{\contentsline {paragraph}{最小瓶颈生成树}{76}{subsection.15.8.4}}
\@writefile{toc}{\contentsline {paragraph}{最小瓶颈路}{76}{subsection.15.8.4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.8.5}次小生成树($O(V^2)$)}{76}{subsection.15.8.5}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.8.6}第k小生成树}{78}{subsection.15.8.6}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.8.7}最优比例生成树(未知复杂度)}{78}{subsection.15.8.7}}
\@writefile{toc}{\contentsline {subsubsection}{Dinkelbach 版(优于二分)}{78}{subsection.15.8.7}}
\@writefile{toc}{\contentsline {subsubsection}{二分版}{80}{subsection.15.8.7}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.8.8}有向图最小树形图($O(VE)$)}{81}{subsection.15.8.8}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.8.9}最小度限制生成树}{83}{subsection.15.8.9}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.8.10}最小生成森林($k$颗树)：改进Kruskal($O(E \qopname \relax o{lg}E)$)}{83}{subsection.15.8.10}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.8.11}平面点的欧几里德最小生成树($O(V^2)$)}{83}{subsection.15.8.11}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.8.12}平面点的曼哈顿最小生成树与莫队算法}{83}{subsection.15.8.12}}
\@writefile{toc}{\contentsline {subsubsection}{朴素算法($O(V^2)$)}{83}{subsection.15.8.12}}
\@writefile{toc}{\contentsline {subsubsection}{莫队算法中的最小生成树($O(VlgV)$)}{84}{subsection.15.8.12}}
\@writefile{toc}{\contentsline {paragraph}{POJ 3241 Object Clustering}{84}{subsection.15.8.12}}
\@writefile{toc}{\contentsline {subsubsection}{莫队算法$(O(N^{1.5}))$(用于无修改区间查询)}{87}{subsection.15.8.12}}
\@writefile{toc}{\contentsline {paragraph}{莫队算法}{87}{subsection.15.8.12}}
\@writefile{toc}{\contentsline {paragraph}{曼哈顿最小生成树版本([2009国家集训队]小Z的袜子(hose),3284ms)}{87}{subsection.15.8.12}}
\@writefile{toc}{\contentsline {paragraph}{无生成树版本([2009国家集训队]小Z的袜子(hose),884ms)}{92}{subsection.15.8.12}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.8.13}最小平衡生成树}{94}{subsection.15.8.13}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.8.14}生成树计数(Matrix-Tree定理)}{94}{subsection.15.8.14}}
\@writefile{toc}{\contentsline {paragraph}{Matrix-Tree定理(Kirchhoff矩阵-树定理)}{94}{subsection.15.8.14}}
\@writefile{toc}{\contentsline {paragraph}{SPOJ HIGH Highways}{94}{Item.26}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.8.15}最小生成树计数(BZOJ 1016)}{96}{subsection.15.8.15}}
\@writefile{toc}{\contentsline {section}{\numberline {15.9}最短路径}{100}{section.15.9}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.9.1}有向无环图的最短路径：拓扑排序($O(N+E)$)}{100}{subsection.15.9.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.9.2}非负权值加权图的最短路径：朴素Dijkstra算法(适用稠密图)($O(V^2)$)}{101}{subsection.15.9.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.9.3}非负权值加权图的最短路径：Dijkstra算法(二叉堆优化)($O((E+V)\qopname \relax o{lg}V)$)}{102}{subsection.15.9.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.9.4}非负权值加权图的最短路径：Dijkstra 算法(优先队列优化)}{104}{subsection.15.9.4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.9.5}含负权值加权图的单源最短路径：Bellman-Ford 算法(适用负环未知)($O(VE)$)}{105}{subsection.15.9.5}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.9.6}含负权值加权图的单源最短路径：Bellman-Ford 算法(栈优化，适用负环未知)($O(VE)$)}{107}{subsection.15.9.6}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.9.7}含负权值加权图的单源最短路径：Spfa 算法(稀疏图)($O(KE)$)}{108}{subsection.15.9.7}}
\@writefile{toc}{\contentsline {paragraph}{朴素SPFA}{108}{subsection.15.9.7}}
\@writefile{toc}{\contentsline {paragraph}{SLF优化的SPFA}{110}{subsection.15.9.7}}
\@writefile{toc}{\contentsline {subsubsection}{SPFA求包含原点闭环的最短路(邻接矩阵版)}{112}{subsection.15.9.7}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.9.8}全源最短路径：Floyd 算法($O(V^3)$)}{114}{subsection.15.9.8}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.9.9}全源最短路径：Johnson 算法(稀疏图)($O(EV\qopname \relax o{lg}V)$)}{115}{subsection.15.9.9}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.9.10}次短路径}{115}{subsection.15.9.10}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.9.11}第k短路径}{117}{subsection.15.9.11}}
\@writefile{toc}{\contentsline {subsubsection}{第k短路径: A*}{117}{subsection.15.9.11}}
\@writefile{toc}{\contentsline {subsubsection}{前k短路径: Dijkstra变形}{120}{subsection.15.9.11}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.9.12}差分约束系统：SPFA($O(KE)$)}{121}{subsection.15.9.12}}
\@writefile{toc}{\contentsline {subsubsection}{Theorm}{121}{subsection.15.9.12}}
\@writefile{toc}{\contentsline {subsubsection}{模板：SPFA($O(KE)$)}{121}{subsection.15.9.12}}
\@writefile{toc}{\contentsline {paragraph}{邻接表版}{121}{subsection.15.9.12}}
\@writefile{toc}{\contentsline {paragraph}{带负环的情况：Bellman-Ford}{123}{subsection.15.9.12}}
\@writefile{toc}{\contentsline {subparagraph}{一道例题：HDU 3776 Task}{123}{subsection.15.9.12}}
\@writefile{toc}{\contentsline {subparagraph}{上题另解}{125}{subsection.15.9.12}}
\@writefile{toc}{\contentsline {paragraph}{邻接矩阵版}{128}{subsection.15.9.12}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.9.13}平面点对的最短路径(优化)}{128}{subsection.15.9.13}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.9.14}双标准限制最短路径}{128}{subsection.15.9.14}}
\@writefile{toc}{\contentsline {section}{\numberline {15.10}匹配}{128}{section.15.10}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.10.1}二分图最大匹配：Hungary算法($O(VE)$)}{128}{subsection.15.10.1}}
\@writefile{toc}{\contentsline {subsubsection}{主框架}{128}{subsection.15.10.1}}
\@writefile{toc}{\contentsline {subsubsection}{邻接矩阵实现}{129}{subsection.15.10.1}}
\@writefile{toc}{\contentsline {subsubsection}{链式前向星实现}{130}{subsection.15.10.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.10.2}大数据二分图最大匹配：Hopcroft-Karp($O(\sqrt {V}E)$)}{131}{subsection.15.10.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.10.3}二分图多重匹配：Hungary算法改($O(VE)$)}{133}{subsection.15.10.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.10.4}二分图的几个等价}{134}{subsection.15.10.4}}
\@writefile{toc}{\contentsline {paragraph}{最大边独立集}{134}{subsection.15.10.4}}
\@writefile{toc}{\contentsline {paragraph}{最大独立集}{134}{subsection.15.10.4}}
\@writefile{toc}{\contentsline {paragraph}{最小支配集}{134}{subsection.15.10.4}}
\@writefile{toc}{\contentsline {paragraph}{最大团}{134}{subsection.15.10.4}}
\@writefile{toc}{\contentsline {paragraph}{最小点覆盖}{134}{subsection.15.10.4}}
\@writefile{toc}{\contentsline {paragraph}{最小路径覆盖}{134}{subsection.15.10.4}}
\@writefile{toc}{\contentsline {paragraph}{等价}{134}{subsection.15.10.4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.10.5}二分图带权(最大/最小)完备匹配：Kuhn-Munkras算法($O(N^3)$)}{134}{subsection.15.10.5}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.10.6}一般图最大匹配：带花树算法(未知复杂度)}{136}{subsection.15.10.6}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.10.7}稳定婚姻匹配($O(N^2)$)}{139}{subsection.15.10.7}}
\@writefile{toc}{\contentsline {section}{\numberline {15.11}网络流}{141}{section.15.11}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.11.1}最大流：Edmonds Karp ($O(V*E^2)$)}{141}{subsection.15.11.1}}
\@writefile{toc}{\contentsline {subsubsection}{无打印路径}{141}{subsection.15.11.1}}
\@writefile{toc}{\contentsline {subsubsection}{带打印路径}{142}{subsection.15.11.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.11.2}最大流最小割：加各种优化的Dinic算法($O(V^2E)$)}{144}{subsection.15.11.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.11.3}最大流最小割：加各种优化的ISAP算法($O(V^2E)$)}{149}{subsection.15.11.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.11.4}最大流最小割：加各种优化的HLPP算法($O(V^2\sqrt {E})$)}{153}{subsection.15.11.4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.11.5}贪心预流：用于分层图Dinic预处理(ZOJ 2364)}{157}{subsection.15.11.5}}
\@writefile{toc}{\contentsline {subsubsection}{示例：ZOJ 2364}{158}{subsection.15.11.5}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.11.6}有上下界的网络流}{163}{subsection.15.11.6}}
\@writefile{toc}{\contentsline {subsubsection}{无源汇最大流}{163}{subsection.15.11.6}}
\@writefile{toc}{\contentsline {paragraph}{原理}{163}{subsection.15.11.6}}
\@writefile{toc}{\contentsline {paragraph}{例：SGU 194 Reactor Cooling}{163}{Item.29}}
\@writefile{toc}{\contentsline {subsubsection}{有源汇最大流}{168}{Item.29}}
\@writefile{toc}{\contentsline {paragraph}{原理}{168}{Item.29}}
\@writefile{toc}{\contentsline {paragraph}{例：ZOJ 3229 Shoot the Bullet}{168}{Item.29}}
\@writefile{toc}{\contentsline {subsubsection}{有源汇最小流}{168}{Item.29}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.11.7}最小(大)费用最大流：SPFA增广路($O(w*O(SPFA))$)}{168}{subsection.15.11.7}}
\@writefile{toc}{\contentsline {subsubsection}{ZKW版}{168}{subsection.15.11.7}}
\@writefile{toc}{\contentsline {subsubsection}{普通版}{171}{subsection.15.11.7}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.11.8}判网络流有多解}{173}{subsection.15.11.8}}
\@writefile{toc}{\contentsline {paragraph}{方法1(较慢)：}{173}{subsection.15.11.8}}
\@writefile{toc}{\contentsline {paragraph}{方法2(很快)：}{173}{subsection.15.11.8}}
\@writefile{toc}{\contentsline {paragraph}{例：HDU 4975}{174}{subsection.15.11.8}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.11.9}判断最小割唯一}{179}{subsection.15.11.9}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.11.10}最大权闭合子图}{180}{subsection.15.11.10}}
\@writefile{toc}{\contentsline {paragraph}{闭合图}{180}{subsection.15.11.10}}
\@writefile{toc}{\contentsline {paragraph}{最大权闭合子图}{180}{subsection.15.11.10}}
\@writefile{toc}{\contentsline {paragraph}{建图}{180}{subsection.15.11.10}}
\@writefile{toc}{\contentsline {paragraph}{例：SPOJ PROFIT Maximum Profit}{180}{subsection.15.11.10}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.11.11}最大密度子图}{184}{subsection.15.11.11}}
\@writefile{toc}{\contentsline {paragraph}{密度}{184}{subsection.15.11.11}}
\@writefile{toc}{\contentsline {paragraph}{最大密度子图}{184}{subsection.15.11.11}}
\@writefile{toc}{\contentsline {paragraph}{方法}{184}{subsection.15.11.11}}
\@writefile{toc}{\contentsline {paragraph}{边带权拓广}{184}{subsection.15.11.11}}
\@writefile{toc}{\contentsline {paragraph}{点边带权拓广}{185}{subsection.15.11.11}}
\@writefile{toc}{\contentsline {paragraph}{例：POJ 3155 Hard Life(不带权，输出点集)}{185}{subsection.15.11.11}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.11.12}混合图(有向+无向)的欧拉路径}{186}{subsection.15.11.12}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.11.13}二分图最小点权覆盖}{186}{subsection.15.11.13}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.11.14}二分图最大点权独立集}{186}{subsection.15.11.14}}
\@writefile{toc}{\contentsline {paragraph}{例：HDU 1569}{186}{subsection.15.11.14}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.11.15}最小K路径覆盖}{190}{subsection.15.11.15}}
\@writefile{toc}{\contentsline {subsection}{\numberline {15.11.16}点连通度与边连通度}{196}{subsection.15.11.16}}
\@writefile{toc}{\contentsline {paragraph}{连通度问题}{196}{subsection.15.11.16}}
\@writefile{toc}{\contentsline {paragraph}{点连通度}{196}{subsection.15.11.16}}
\@writefile{toc}{\contentsline {paragraph}{边连通度}{196}{subsection.15.11.16}}
\@writefile{toc}{\contentsline {paragraph}{有向图点连通度}{196}{subsection.15.11.16}}
\@writefile{toc}{\contentsline {paragraph}{有向图边连通度}{196}{subsection.15.11.16}}
\@writefile{toc}{\contentsline {paragraph}{无向图}{196}{subsection.15.11.16}}
\@writefile{toc}{\contentsline {paragraph}{混合图}{196}{subsection.15.11.16}}
\@writefile{toc}{\contentsline {paragraph}{点或边带权}{196}{subsection.15.11.16}}
\@writefile{toc}{\contentsline {chapter}{\numberline {16}Dynamic Programming}{197}{chapter.16}}
\@writefile{lof}{\addvspace {10\p@ }}
\@writefile{lot}{\addvspace {10\p@ }}
\@writefile{toc}{\contentsline {section}{\numberline {16.1}线性模型}{197}{section.16.1}}
\@writefile{toc}{\contentsline {section}{\numberline {16.2}串模型}{197}{section.16.2}}
\@writefile{toc}{\contentsline {section}{\numberline {16.3}状态压缩模型}{197}{section.16.3}}
\@writefile{toc}{\contentsline {section}{\numberline {16.4}四边形优化}{197}{section.16.4}}
\@writefile{toc}{\contentsline {subsection}{\numberline {16.4.1}朴素四边形优化}{197}{subsection.16.4.1}}
\@writefile{toc}{\contentsline {paragraph}{POJ 1738 An old Stone Game}{198}{subsection.16.4.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {16.4.2}GarsiaWachs算法(POJ 1738 An old Stone Game)}{198}{subsection.16.4.2}}
\@writefile{toc}{\contentsline {section}{\numberline {16.5}经典问题}{200}{section.16.5}}
\@writefile{toc}{\contentsline {subsection}{\numberline {16.5.1}最长上升子序列 LIS}{200}{subsection.16.5.1}}
\@writefile{toc}{\contentsline {subsection}{\numberline {16.5.2}最长公共子序列 LCS}{200}{subsection.16.5.2}}
\@writefile{toc}{\contentsline {subsubsection}{Subsequence(不连续)}{200}{subsection.16.5.2}}
\@writefile{toc}{\contentsline {subsubsection}{Substring(连续)}{200}{subsection.16.5.2}}
\@writefile{toc}{\contentsline {subsubsection}{相同位置相同}{201}{subsection.16.5.2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {16.5.3}最大子矩阵和(Ural 1146)}{201}{subsection.16.5.3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {16.5.4}类TSP问题(状压DP)(POJ 3311 Hie with the Pie)}{202}{subsection.16.5.4}}
\@writefile{toc}{\contentsline {chapter}{\numberline {17}Other Algorithms}{205}{chapter.17}}
\@writefile{lof}{\addvspace {10\p@ }}
\@writefile{lot}{\addvspace {10\p@ }}
\@writefile{toc}{\contentsline {section}{\numberline {17.1}Get Min(A[i]-A[j]) (0,1,2,\dots ,n-1)}{205}{section.17.1}}
\@writefile{toc}{\contentsline {section}{\numberline {17.2}Get a Circle (Floyd)}{205}{section.17.2}}
\@writefile{toc}{\contentsline {section}{\numberline {17.3}Meet in the Middle}{205}{section.17.3}}
\@writefile{toc}{\contentsline {part}{V\hspace {1em}Classic Problems}{207}{part.5}}
\newlabel{LastPage}{{}{208}{}{page.208}{}}
\xdef\lastpage@lastpage{208}
\xdef\lastpage@lastpageHy{208}