-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathgraph-algorithms-summary.html
779 lines (615 loc) · 132 KB
/
graph-algorithms-summary.html
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
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
<!DOCTYPE html>
<html lang="zh-CN,default">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 4.2.1">
<link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
<link rel="icon" type="image/png" sizes="32x32" href="/images/favicom-32x32-logo.png">
<link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-logo.png">
<link rel="mask-icon" href="/images/logo.svg" color="#222">
<meta name="google-site-verification" content="ROUQoZovui7E3zu9iZWkJdCuxBSmH6dcEV2qncmZ4DQ">
<meta name="msvalidate.01" content="A5DD278FA75034DFB543D13A5DEF0F94">
<meta name="baidu-site-verification" content="h7T48zL37w">
<link rel="stylesheet" href="/css/main.css">
<link rel="stylesheet" href="/lib/font-awesome/css/all.min.css">
<script id="hexo-configurations">
var NexT = window.NexT || {};
var CONFIG = {"hostname":"blog.charfole.top","root":"/","scheme":"Gemini","version":"7.8.0","exturl":true,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":true,"scrollpercent":true},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
</script>
<meta name="description" content="前言最近在 AcWing 学习图论算法，包含了图的存储、搜索、拓扑排序、最短路算法、最小生成树算法、二分图算法等知识。因为涉及到的内容和代码较多，所以将这些内容汇总成笔记，以便日后回顾。">
<meta property="og:type" content="article">
<meta property="og:title" content="图论算法总结（搜索、拓扑排序、最短路、最小生成树、二分图）">
<meta property="og:url" content="https://blog.charfole.top/graph-algorithms-summary.html">
<meta property="og:site_name" content="Charfole's Blog">
<meta property="og:description" content="前言最近在 AcWing 学习图论算法，包含了图的存储、搜索、拓扑排序、最短路算法、最小生成树算法、二分图算法等知识。因为涉及到的内容和代码较多，所以将这些内容汇总成笔记，以便日后回顾。">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2021-12-26T01:36:51.000Z">
<meta property="article:modified_time" content="2023-09-21T09:33:05.649Z">
<meta property="article:author" content="Charfole">
<meta property="article:tag" content="Notes">
<meta property="article:tag" content="Algorithm">
<meta property="article:tag" content="Data Structrue">
<meta property="article:tag" content="Graph theory">
<meta name="twitter:card" content="summary">
<link rel="canonical" href="https://blog.charfole.top/graph-algorithms-summary.html">
<script id="page-configurations">
// https://hexo.io/docs/variables.html
CONFIG.page = {
sidebar: "",
isHome : false,
isPost : true,
lang : 'zh-CN'
};
</script>
<title>图论算法总结（搜索、拓扑排序、最短路、最小生成树、二分图） | Charfole's Blog</title>
<script async src="https://www.googletagmanager.com/gtag/js?id=UA-174017535-1"></script>
<script>
if (CONFIG.hostname === location.hostname) {
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'UA-174017535-1');
}
</script>
<noscript>
<style>
.use-motion .brand,
.use-motion .menu-item,
.sidebar-inner,
.use-motion .post-block,
.use-motion .pagination,
.use-motion .comments,
.use-motion .post-header,
.use-motion .post-body,
.use-motion .collection-header { opacity: initial; }
.use-motion .site-title,
.use-motion .site-subtitle {
opacity: initial;
top: initial;
}
.use-motion .logo-line-before i { left: initial; }
.use-motion .logo-line-after i { right: initial; }
</style>
</noscript>
<link rel="alternate" href="/atom.xml" title="Charfole's Blog" type="application/atom+xml">
</head>
<body itemscope itemtype="http://schema.org/WebPage">
<div class="container use-motion">
<div class="headband"></div>
<header class="header" itemscope itemtype="http://schema.org/WPHeader">
<div class="header-inner"><div class="site-brand-container">
<div class="site-nav-toggle">
<div class="toggle" aria-label="切换导航栏">
<span class="toggle-line toggle-line-first"></span>
<span class="toggle-line toggle-line-middle"></span>
<span class="toggle-line toggle-line-last"></span>
</div>
</div>
<div class="site-meta">
<a href="/" class="brand" rel="start">
<span class="logo-line-before"><i></i></span>
<h1 class="site-title">Charfole's Blog</h1>
<span class="logo-line-after"><i></i></span>
</a>
</div>
<div class="site-nav-right">
<div class="toggle popup-trigger">
<i class="fa fa-search fa-fw fa-lg"></i>
</div>
</div>
</div>
<nav class="site-nav">
<ul id="menu" class="main-menu menu">
<li class="menu-item menu-item-home">
<a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>
</li>
<li class="menu-item menu-item-archives">
<a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>
</li>
<li class="menu-item menu-item-tags">
<a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>
</li>
<li class="menu-item menu-item-categories">
<a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a>
</li>
<li class="menu-item menu-item-search">
<a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
</a>
</li>
</ul>
</nav>
<div class="search-pop-overlay">
<div class="popup search-popup">
<div class="search-header">
<span class="search-icon">
<i class="fa fa-search"></i>
</span>
<div class="search-input-container">
<input autocomplete="off" autocapitalize="off"
placeholder="搜索..." spellcheck="false"
type="search" class="search-input">
</div>
<span class="popup-btn-close">
<i class="fa fa-times-circle"></i>
</span>
</div>
<div id="search-result">
<div id="no-result">
<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
</div>
</div>
</div>
</div>
</div>
</header>
<div class="reading-progress-bar"></div>
<main class="main">
<div class="main-inner">
<div class="content-wrap">
<div class="content post posts-expand">
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="https://blog.charfole.top/graph-algorithms-summary.html">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Charfole">
<meta itemprop="description" content="Carpe diem">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Charfole's Blog">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
图论算法总结（搜索、拓扑排序、最短路、最小生成树、二分图）
</h1>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2021-12-26 09:36:51" itemprop="dateCreated datePublished" datetime="2021-12-26T09:36:51+08:00">2021-12-26</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">更新于</span>
<time title="修改时间：2023-09-21 17:33:05" itemprop="dateModified" datetime="2023-09-21T17:33:05+08:00">2023-09-21</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">数据结构与算法</span></a>
</span>
</span>
<span class="post-meta-item" title="阅读次数" id="busuanzi_container_page_pv" style="display: none;">
<span class="post-meta-item-icon">
<i class="fa fa-eye"></i>
</span>
<span class="post-meta-item-text">阅读次数：</span>
<span id="busuanzi_value_page_pv"></span>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-comment"></i>
</span>
<span class="post-meta-item-text">Valine：</span>
<a title="valine" href="/graph-algorithms-summary.html#valine-comments" itemprop="discussionUrl">
<span class="post-comments-count valine-comment-count" data-xid="/graph-algorithms-summary.html" itemprop="commentCount"></span>
</a>
</span>
<br>
<span class="post-meta-item" title="本文字数">
<span class="post-meta-item-icon">
<i class="far fa-file-word"></i>
</span>
<span class="post-meta-item-text">本文字数：</span>
<span>16k</span>
</span>
<span class="post-meta-item" title="阅读时长">
<span class="post-meta-item-icon">
<i class="far fa-clock"></i>
</span>
<span class="post-meta-item-text">阅读时长 ≈</span>
<span>14 分钟</span>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h2><p>最近在 <span class="exturl" data-url="aHR0cHM6Ly93d3cuYWN3aW5nLmNvbS9hY3Rpdml0eS9jb250ZW50LzExLw==">AcWing<i class="fa fa-external-link-alt"></i></span> 学习图论算法，包含了图的存储、搜索、拓扑排序、最短路算法、最小生成树算法、二分图算法等知识。因为涉及到的内容和代码较多，所以将这些内容汇总成笔记，以便日后回顾。<br><a id="more"></a></p>
<h2 id="树的存储和图的存储"><a href="#树的存储和图的存储" class="headerlink" title="树的存储和图的存储"></a>树的存储和图的存储</h2><ul>
<li><p><strong>邻接矩阵</strong></p>
<p>空间开销为点的数目的平方，当图较为稠密时使用，稀疏图的话会有很多矩阵中的元素没有值，浪费掉了。存储方式使用一个二维矩阵即可。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> N;</span><br><span class="line"><span class="keyword">int</span> graph[N][N];</span><br></pre></td></tr></table></figure>
</li>
<li><p><strong>邻接表</strong></p>
<p>空间开销为边的数目，当图较为稀疏的时候使用，存储方式为一个多层链表，即每个顶点都有一个专属的链表，每个链表中存着与当前顶点有边的其他顶点。初始化的代码如下所示：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> N, M;</span><br><span class="line"><span class="comment">// 下面几个变量存储的分别为各个顶点的链表头，当前边的终点，当前边的权值，下一条边的编号，和当前边的编号 </span></span><br><span class="line"><span class="keyword">int</span> h[N], e[M], w[M], ne[M], idx = <span class="number">0</span>;</span><br><span class="line"><span class="built_in">memset</span>(h, <span class="number">-1</span>, <span class="keyword">sizeof</span>(h));</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b, <span class="keyword">int</span> c)</span> </span>{</span><br><span class="line"> <span class="comment">// 更新当前边的终点，当前边的权值，当前边下一条边的序号和头插法更新当前顶点连接的第一条边</span></span><br><span class="line"> e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</li>
</ul>
<h2 id="树与图的搜索"><a href="#树与图的搜索" class="headerlink" title="树与图的搜索"></a>树与图的搜索</h2><ul>
<li><p><strong>深度优先搜索</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> u)</span> </span>{</span><br><span class="line"> st[u] = <span class="literal">true</span>;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = h[u]; i != <span class="number">-1</span>; i = ne[i]) {</span><br><span class="line"> <span class="keyword">int</span> j = e[i];</span><br><span class="line"> <span class="keyword">if</span> (!st[j]) dfs(j);</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p><span class="exturl" data-url="aHR0cHM6Ly93d3cuYWN3aW5nLmNvbS9hY3Rpdml0eS9jb250ZW50L3Byb2JsZW0vY29udGVudC85MDkv">例题：树的重心<i class="fa fa-external-link-alt"></i></span></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">1e5</span> + <span class="number">5</span>, M = <span class="number">2</span> * N;</span><br><span class="line"><span class="keyword">int</span> ans = N;</span><br><span class="line"><span class="keyword">int</span> n;</span><br><span class="line"><span class="keyword">bool</span> st[N];</span><br><span class="line"><span class="keyword">int</span> h[N], e[M], ne[M], idx = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b)</span> </span>{</span><br><span class="line"> e[idx] = b, ne[idx] = h[a], h[a] = idx++;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> u)</span> </span>{</span><br><span class="line"> st[u] = <span class="literal">true</span>;</span><br><span class="line"> <span class="keyword">int</span> res = <span class="number">0</span>, sum = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = h[u]; i != <span class="number">-1</span>; i = ne[i]) {</span><br><span class="line"> <span class="keyword">int</span> j = e[i];</span><br><span class="line"> <span class="keyword">if</span> (st[j]) <span class="keyword">continue</span>;</span><br><span class="line"> <span class="keyword">int</span> s = dfs(j);</span><br><span class="line"> res = max(res, s);</span><br><span class="line"> sum += s;</span><br><span class="line"> }</span><br><span class="line"> res = max(res, n - sum);</span><br><span class="line"> ans = min(ans, res);</span><br><span class="line"> <span class="keyword">return</span> sum;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">memset</span>(h, <span class="number">-1</span> ,<span class="keyword">sizeof</span>(h));</span><br><span class="line"> <span class="built_in">cin</span> >> n;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i < n; i++) {</span><br><span class="line"> <span class="keyword">int</span> a, b;</span><br><span class="line"> <span class="built_in">cin</span> >> a >> b;</span><br><span class="line"> add(a, b);</span><br><span class="line"> add(b, a);</span><br><span class="line"> }</span><br><span class="line"> dfs(<span class="number">1</span>);</span><br><span class="line"> <span class="built_in">cout</span> << ans << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</li>
<li><p><strong>宽度优先搜索</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">queue</span><<span class="keyword">int</span>> q;</span><br><span class="line">st[<span class="number">1</span>] = <span class="literal">true</span>;</span><br><span class="line">q.push(<span class="number">1</span>);</span><br><span class="line"></span><br><span class="line"><span class="keyword">while</span> (q.size()) {</span><br><span class="line"> <span class="keyword">int</span> t = q.front();</span><br><span class="line"> q.pop();</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = h[t]; i != <span class="number">-1</span>; i = ne[i]) {</span><br><span class="line"> <span class="keyword">int</span> j = e[i];</span><br><span class="line"> <span class="keyword">if</span> (!st[j]) {</span><br><span class="line"> st[j] = <span class="literal">true</span>;</span><br><span class="line"> q.push(j);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p><span class="exturl" data-url="aHR0cHM6Ly93d3cuYWN3aW5nLmNvbS9wcm9ibGVtL2NvbnRlbnQvODQ5Lw==">例题：图中点的层次<i class="fa fa-external-link-alt"></i></span></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">1e5</span> + <span class="number">5</span>;</span><br><span class="line"><span class="keyword">int</span> h[N], e[N], ne[N], idx = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">int</span> d[N];</span><br><span class="line"><span class="keyword">bool</span> st[N];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b)</span> </span>{</span><br><span class="line"> e[idx] = b, ne[idx] = h[a], h[a] = idx++;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> n, m;</span><br><span class="line"> <span class="built_in">cin</span> >> n >> m;</span><br><span class="line"> <span class="comment">// init the distance and the adj list</span></span><br><span class="line"> <span class="built_in">memset</span>(h, <span class="number">-1</span>, <span class="keyword">sizeof</span>(h));</span><br><span class="line"> <span class="built_in">memset</span>(d, <span class="number">-1</span>, <span class="keyword">sizeof</span>(d));</span><br><span class="line"> <span class="keyword">while</span> (m--) {</span><br><span class="line"> <span class="keyword">int</span> a, b;</span><br><span class="line"> <span class="built_in">cin</span> >> a >> b;</span><br><span class="line"> add(a, b);</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">queue</span><<span class="keyword">int</span>> q;</span><br><span class="line"> <span class="comment">// push the starting point</span></span><br><span class="line"> q.push(<span class="number">1</span>);</span><br><span class="line"> d[<span class="number">1</span>] = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">while</span>(q.size()) {</span><br><span class="line"> <span class="keyword">int</span> u = q.front();</span><br><span class="line"> q.pop();</span><br><span class="line"> <span class="comment">// iterate all the linked point of current point</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = h[u]; i != <span class="number">-1</span>; i = ne[i]) {</span><br><span class="line"> <span class="keyword">int</span> j = e[i];</span><br><span class="line"> <span class="comment">// push the point into the queue</span></span><br><span class="line"> <span class="keyword">if</span> (!st[j]) {</span><br><span class="line"> st[j] = <span class="literal">true</span>;</span><br><span class="line"> q.push(j);</span><br><span class="line"> <span class="comment">// update the distance</span></span><br><span class="line"> d[j] = d[u] + <span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">cout</span> << d[n] << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</li>
</ul>
<h2 id="拓扑排序"><a href="#拓扑排序" class="headerlink" title="拓扑排序"></a>拓扑排序</h2><ul>
<li><p><strong>思想：</strong>邻接表存图，存完之后看看有没有入度为0的点，有的话将其加入队列，之后利用BFS的过程，每次遍历一个点，将其导出的边取消掉，从而获得新的入度为0的点，直至所有点都被遍历到。</p>
</li>
<li><p><a href="https://www.acwing.com/problem/content/850/" target="_blank" rel="noopener">例题<strong>：</strong>拓扑排序</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">1e5</span> + <span class="number">5</span>, M = <span class="number">2</span> * N;</span><br><span class="line"><span class="keyword">int</span> h[N], e[M], ne[M], idx = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">int</span> d[N];</span><br><span class="line"><span class="keyword">int</span> top[N];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b)</span> </span>{</span><br><span class="line"> e[idx] = b, ne[idx] = h[a], h[a] = idx++;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> n, m, a, b, cnt = <span class="number">0</span>;</span><br><span class="line"> <span class="built_in">memset</span>(h, <span class="number">-1</span>, <span class="keyword">sizeof</span>(h));</span><br><span class="line"> <span class="built_in">cin</span> >> n >> m;</span><br><span class="line"> <span class="keyword">while</span>(m--) {</span><br><span class="line"> <span class="built_in">cin</span> >> a >> b;</span><br><span class="line"> add(a, b);</span><br><span class="line"> d[b]++;</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">queue</span><<span class="keyword">int</span>> q;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i <= n; i++) {</span><br><span class="line"> <span class="keyword">if</span> (!d[i]) q.push(i);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">while</span>(q.size()) {</span><br><span class="line"> <span class="keyword">int</span> cur = q.front();</span><br><span class="line"> q.pop();</span><br><span class="line"> top[cnt++] = cur;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = h[cur]; i != <span class="number">-1</span>; i = ne[i]) {</span><br><span class="line"> <span class="keyword">int</span> j = e[i];</span><br><span class="line"> d[j]--;</span><br><span class="line"> <span class="keyword">if</span> (!d[j]) {</span><br><span class="line"> q.push(j);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (cnt != n) <span class="built_in">cout</span> << <span class="number">-1</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < n; i++) {</span><br><span class="line"> <span class="built_in">cout</span> << top[i] << <span class="string">" "</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">cout</span> << <span class="built_in">endl</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</li>
</ul>
<h2 id="最短路算法"><a href="#最短路算法" class="headerlink" title="最短路算法"></a>最短路算法</h2><h3 id="Dijkstra-算法（单源最短路）"><a href="#Dijkstra-算法（单源最短路）" class="headerlink" title="Dijkstra 算法（单源最短路）"></a>Dijkstra 算法（单源最短路）</h3><ul>
<li><p><strong>思想：</strong>每次找到当前距离源点最近的一个点，将其序号记录下来，同时以该点为中转点，更新（松弛）其他点到源点的距离。重复上述的过程 n - 1 次，即可更新所有点，获得答案。</p>
</li>
<li><p><span class="exturl" data-url="aHR0cHM6Ly93d3cuYWN3aW5nLmNvbS9wcm9ibGVtL2NvbnRlbnQvODUxLw==">例题：最短路<i class="fa fa-external-link-alt"></i></span></p>
<p><strong>邻接矩阵版本（复杂度：O(N * N)）</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">505</span>;</span><br><span class="line"><span class="keyword">int</span> g[N][N];</span><br><span class="line"><span class="keyword">int</span> dist[N];</span><br><span class="line"><span class="keyword">bool</span> st[N];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> n, m;</span><br><span class="line"> <span class="built_in">cin</span> >> n >> m;</span><br><span class="line"> <span class="comment">// init the distance and adj matrix</span></span><br><span class="line"> <span class="built_in">memset</span>(dist, <span class="number">0x3f</span>, <span class="keyword">sizeof</span>(dist));</span><br><span class="line"> <span class="built_in">memset</span>(g, <span class="number">0x3f</span>, <span class="keyword">sizeof</span>(g));</span><br><span class="line"> <span class="comment">// build the adj matrix and remove the repeated edge</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < m; i++) {</span><br><span class="line"> <span class="keyword">int</span> a, b, c;</span><br><span class="line"> <span class="built_in">cin</span> >> a >> b >> c;</span><br><span class="line"> g[a][b] = min(g[a][b], c);</span><br><span class="line"> }</span><br><span class="line"> dist[<span class="number">1</span>] = <span class="number">0</span>;</span><br><span class="line"> <span class="comment">// dijkstra, iterate n - 1 times</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < n - <span class="number">1</span>; i++) {</span><br><span class="line"> <span class="keyword">int</span> t = <span class="number">-1</span>;</span><br><span class="line"> <span class="comment">// search the nearest and unvisited point to the start</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j <= n; j++) {</span><br><span class="line"> <span class="keyword">if</span> (!st[j] && (t == <span class="number">-1</span> || dist[j] < dist[t])) {</span><br><span class="line"> t = j;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> </span><br><span class="line"> <span class="comment">// update the other points through current point</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i <= n; i++) {</span><br><span class="line"> dist[i] = min(dist[i], dist[t] + g[t][i]);</span><br><span class="line"> }</span><br><span class="line"> </span><br><span class="line"> <span class="comment">// mark visited</span></span><br><span class="line"> st[t] = <span class="literal">true</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (dist[n] > <span class="number">0x3f3f3f3f</span> / <span class="number">2</span>) <span class="built_in">cout</span> << <span class="number">-1</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">cout</span> << dist[n] << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</li>
</ul>
<ul>
<li><p><strong>邻接表版本（复杂度：O(MN)）</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">505</span>, M = <span class="number">1e5</span> + <span class="number">5</span>;</span><br><span class="line"><span class="keyword">int</span> h[N], e[M], ne[M], w[M], idx = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">int</span> dist[N];</span><br><span class="line"><span class="keyword">bool</span> st[N];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b, <span class="keyword">int</span> c)</span> </span>{</span><br><span class="line"> e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> n, m;</span><br><span class="line"> <span class="built_in">cin</span> >> n >> m;</span><br><span class="line"> <span class="comment">// init the distance and adj list</span></span><br><span class="line"> <span class="built_in">memset</span>(dist, <span class="number">0x3f</span>, <span class="keyword">sizeof</span>(dist));</span><br><span class="line"> <span class="built_in">memset</span>(h, <span class="number">-1</span>, <span class="keyword">sizeof</span>(h));</span><br><span class="line"> <span class="keyword">while</span> (m--) {</span><br><span class="line"> <span class="keyword">int</span> a, b, c;</span><br><span class="line"> <span class="built_in">cin</span> >> a >> b >> c;</span><br><span class="line"> add(a, b, c);</span><br><span class="line"> }</span><br><span class="line"> </span><br><span class="line"> dist[<span class="number">1</span>] = <span class="number">0</span>;</span><br><span class="line"> <span class="comment">// dijkstra: iterate n - 1 times</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < n - <span class="number">1</span>; i++) {</span><br><span class="line"> <span class="keyword">int</span> t = <span class="number">-1</span>;</span><br><span class="line"> <span class="comment">// search the nearest and unvisited point to the start</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i <= n; i++) {</span><br><span class="line"> <span class="keyword">if</span> (!st[i] && (t == <span class="number">-1</span> || dist[t] > dist[i])) {</span><br><span class="line"> t = i;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> st[t] = <span class="literal">true</span>;</span><br><span class="line"> <span class="comment">// update the other points through current point</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = h[t]; i != <span class="number">-1</span>; i = ne[i]) {</span><br><span class="line"> <span class="keyword">int</span> j = e[i];</span><br><span class="line"> dist[j] = min(dist[j], dist[t] + w[i]); </span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span> (dist[n] > <span class="number">0x3f3f3f3f</span> / <span class="number">2</span>) <span class="built_in">cout</span> << <span class="number">-1</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">cout</span> << dist[n] << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</li>
</ul>
<ul>
<li><p><strong>堆优化邻接表版本（复杂度：O(MlogN)）</strong></p>
<p><strong>思想：</strong>用pair小根堆存储与源点最近的点的编号，以及该点到源点的距离。之后小根堆堆顶的邻接表，如松弛了某个别的点，则将该点加入到优先队列中，直至优先队列为空。</p>
<p><span class="exturl" data-url="aHR0cHM6Ly93d3cuYWN3aW5nLmNvbS9wcm9ibGVtL2NvbnRlbnQvODUyLw==">例题：堆优化最短路<i class="fa fa-external-link-alt"></i></span></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">typedef</span> pair<<span class="keyword">int</span>, <span class="keyword">int</span>> PII;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">1e6</span> + <span class="number">5</span>;</span><br><span class="line"><span class="keyword">int</span> h[N], e[N], w[N], ne[N], idx = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">int</span> dist[N];</span><br><span class="line"><span class="keyword">bool</span> st[N];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b, <span class="keyword">int</span> c)</span> </span>{</span><br><span class="line"> e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> n, m;</span><br><span class="line"> <span class="built_in">cin</span> >> n >> m;</span><br><span class="line"> <span class="built_in">memset</span>(h, <span class="number">-1</span>, <span class="keyword">sizeof</span>(h));</span><br><span class="line"> <span class="built_in">memset</span>(dist, <span class="number">0x3f3f3f3f</span>, <span class="keyword">sizeof</span>(dist));</span><br><span class="line"> <span class="keyword">while</span> (m--) {</span><br><span class="line"> <span class="keyword">int</span> a, b, c;</span><br><span class="line"> <span class="built_in">cin</span> >> a >> b >> c;</span><br><span class="line"> add(a, b, c);</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">// init and push the start point</span></span><br><span class="line"> priority_queue<PII, <span class="built_in">vector</span><PII>, greater<PII>> q;</span><br><span class="line"> dist[<span class="number">1</span>] = <span class="number">0</span>;</span><br><span class="line"> q.push({<span class="number">0</span>, <span class="number">1</span>});</span><br><span class="line"> <span class="comment">// iterate the priority_queue</span></span><br><span class="line"> <span class="keyword">while</span>(q.size()) {</span><br><span class="line"> <span class="comment">// get the nearest point</span></span><br><span class="line"> <span class="keyword">auto</span> p = q.top();</span><br><span class="line"> q.pop();</span><br><span class="line"> <span class="comment">// judge visited or not</span></span><br><span class="line"> <span class="keyword">int</span> cur = p.second;</span><br><span class="line"> <span class="keyword">if</span> (st[cur]) <span class="keyword">continue</span>;</span><br><span class="line"> st[cur] = <span class="literal">true</span>;</span><br><span class="line"> <span class="comment">// update all the other points throught current point</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = h[cur]; i != <span class="number">-1</span>; i = ne[i]) {</span><br><span class="line"> <span class="keyword">int</span> j = e[i];</span><br><span class="line"> <span class="keyword">if</span> (dist[j] > dist[cur] + w[i]) {</span><br><span class="line"> dist[j] = dist[cur] + w[i];</span><br><span class="line"> q.push({dist[j], j});</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (dist[n] > <span class="number">0x3f3f3f3f</span> / <span class="number">2</span>) <span class="built_in">cout</span> << <span class="number">-1</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">cout</span> << dist[n] << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</li>
</ul>
<h3 id="Bellman-ford-算法（单源最短路）"><a href="#Bellman-ford-算法（单源最短路）" class="headerlink" title="Bellman-ford 算法（单源最短路）"></a>Bellman-ford 算法（单源最短路）</h3><ul>
<li><p><strong>思想：</strong>该算法可以处理存在负权边（负权回路）的图，进行 n-1 次循环，每次循环将所有的边松弛一下，循环结束后，所有点到源点的距离即为最短距离。同时，可以更改循环次数，从而获得最多经过 k 条边的最短距离。</p>
</li>
<li><p><span class="exturl" data-url="aHR0cHM6Ly93d3cuYWN3aW5nLmNvbS9wcm9ibGVtL2NvbnRlbnQvODU1Lw==">例题：有边数限制的最短路<i class="fa fa-external-link-alt"></i></span></p>
<p><strong>直接存边版本（复杂度：O(M * N)）</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">505</span>, M = <span class="number">1e5</span> + <span class="number">5</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> INF = <span class="number">0x3f3f3f3f</span>;</span><br><span class="line"><span class="keyword">int</span> dist[N], last[N];</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">edge</span> {</span></span><br><span class="line"> <span class="keyword">int</span> a, b, c;</span><br><span class="line">}edges[M];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> n, m, k;</span><br><span class="line"> <span class="built_in">cin</span> >> n >> m >> k;</span><br><span class="line"> <span class="built_in">memset</span>(dist, <span class="number">0x3f</span>, <span class="keyword">sizeof</span>(dist));</span><br><span class="line"> dist[<span class="number">1</span>] = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < m; i++) {</span><br><span class="line"> <span class="keyword">int</span> a, b, c;</span><br><span class="line"> <span class="built_in">cin</span> >> a >> b >> c;</span><br><span class="line"> edges[i] = {a, b, c};</span><br><span class="line"> }</span><br><span class="line"> </span><br><span class="line"> <span class="comment">// iterate k times and update all the edges</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < k; i++) {</span><br><span class="line"> <span class="built_in">memcpy</span>(last, dist, <span class="keyword">sizeof</span>(dist));</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < m; i++) {</span><br><span class="line"> <span class="keyword">auto</span> e = edges[i];</span><br><span class="line"> <span class="keyword">if</span> (dist[e.b] > last[e.a] + e.c) {</span><br><span class="line"> dist[e.b] = last[e.a] + e.c;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">if</span> (dist[n] > INF / <span class="number">2</span>) <span class="built_in">cout</span> << <span class="string">"impossible"</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">cout</span> << dist[n] << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</li>
</ul>
<h3 id="SPFA-算法（单源最短路）"><a href="#SPFA-算法（单源最短路）" class="headerlink" title="SPFA 算法（单源最短路）"></a>SPFA 算法（单源最短路）</h3><ul>
<li><p><strong>思想：</strong>该算法可以处理存在负权边的图，但不能处理负权回路。数据结构采用邻接表，算法思路采用 BFS，利用队列存储距离和顶点号，每次取出队头的顶点后，松弛与该点相连的所有其他点。在BFS的过程中，弹出一个点标记为false，已在队列中的点则不需要重复加入，只需松弛即可。</p>
</li>
<li><p><span class="exturl" data-url="aHR0cHM6Ly93d3cuYWN3aW5nLmNvbS9wcm9ibGVtL2NvbnRlbnQvODUzLw==">例题：spfa求最短路<i class="fa fa-external-link-alt"></i></span></p>
<p><strong>邻接表版本（复杂度：有优化，但最坏仍会达到O(M * N)）</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">typedef</span> pair<<span class="keyword">int</span>, <span class="keyword">int</span>> pii;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">1e5</span> + <span class="number">5</span>;</span><br><span class="line"><span class="keyword">int</span> e[N], w[N], ne[N], h[N], idx = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">int</span> dist[N];</span><br><span class="line"><span class="keyword">bool</span> st[N];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b, <span class="keyword">int</span> c)</span> </span>{</span><br><span class="line"> e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> n, m;</span><br><span class="line"> <span class="built_in">cin</span> >> n >> m;</span><br><span class="line"> <span class="built_in">memset</span>(h, <span class="number">-1</span>, <span class="keyword">sizeof</span>(h));</span><br><span class="line"> <span class="built_in">memset</span>(dist, <span class="number">0x3f</span>, <span class="keyword">sizeof</span>(dist));</span><br><span class="line"> dist[<span class="number">1</span>] = <span class="number">0</span>;</span><br><span class="line"> <span class="built_in">queue</span><pii> q;</span><br><span class="line"> <span class="keyword">while</span> (m--) {</span><br><span class="line"> <span class="keyword">int</span> a, b, c;</span><br><span class="line"> <span class="built_in">cin</span> >> a >> b >> c;</span><br><span class="line"> add(a, b, c);</span><br><span class="line"> }</span><br><span class="line"> q.push({<span class="number">0</span>, <span class="number">1</span>});</span><br><span class="line"> st[<span class="number">1</span>] = <span class="literal">true</span>;</span><br><span class="line"> <span class="comment">// BFS</span></span><br><span class="line"> <span class="keyword">while</span>(q.size()) {</span><br><span class="line"> <span class="keyword">auto</span> p = q.front();</span><br><span class="line"> q.pop();</span><br><span class="line"> <span class="keyword">int</span> cur = p.second;</span><br><span class="line"> st[cur] = <span class="literal">false</span>;</span><br><span class="line"> <span class="comment">// update all the adjacent point</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = h[cur]; i != <span class="number">-1</span>; i = ne[i]) {</span><br><span class="line"> <span class="keyword">int</span> j = e[i];</span><br><span class="line"> <span class="keyword">if</span> (dist[j] > dist[cur] + w[i]) {</span><br><span class="line"> dist[j] = dist[cur] + w[i];</span><br><span class="line"> <span class="comment">// if marked, then no need to push</span></span><br><span class="line"> <span class="keyword">if</span> (!st[j]) {</span><br><span class="line"> st[j] = <span class="literal">true</span>;</span><br><span class="line"> q.push({dist[j], j});</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (dist[n] > <span class="number">0x3f3f3f3f</span> / <span class="number">2</span>) <span class="built_in">cout</span> << <span class="string">"impossible"</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">cout</span> << dist[n] << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</li>
</ul>
<h3 id="SPFA-算法（判断负环）"><a href="#SPFA-算法（判断负环）" class="headerlink" title="SPFA 算法（判断负环）"></a>SPFA 算法（判断负环）</h3><ul>
<li><p><strong>思想：</strong>该算法可以处理存在负权边的图，但不能处理负权回路。数据结构采用邻接表，算法思路采用 BFS，利用队列存储距离和顶点号，每次取出队头的顶点后，松弛与该点相连的所有其他点。在BFS的过程中，弹出一个点标记为false，已在队列中的点则不需要重复加入，只需松弛即可。</p>
</li>
<li><p><span class="exturl" data-url="aHR0cHM6Ly93d3cuYWN3aW5nLmNvbS9wcm9ibGVtL2NvbnRlbnQvZGVzY3JpcHRpb24vODU0Lw==">例题：SPFA判断负环<i class="fa fa-external-link-alt"></i></span></p>
<p><strong>邻接表版本（复杂度：有优化，但最坏仍会达到O(M * N)）</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">1e5</span> + <span class="number">5</span>;</span><br><span class="line"><span class="keyword">int</span> e[N], w[N], ne[N], h[N], idx = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">int</span> dist[N];</span><br><span class="line"><span class="keyword">int</span> cnt[N];</span><br><span class="line"><span class="keyword">bool</span> st[N];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b, <span class="keyword">int</span> c)</span> </span>{</span><br><span class="line"> e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> n, m;</span><br><span class="line"> <span class="built_in">cin</span> >> n >> m;</span><br><span class="line"> <span class="keyword">bool</span> flag = <span class="literal">true</span>;</span><br><span class="line"> <span class="built_in">memset</span>(h, <span class="number">-1</span>, <span class="keyword">sizeof</span>(h));</span><br><span class="line"> <span class="built_in">memset</span>(dist, <span class="number">0x3f</span>, <span class="keyword">sizeof</span>(dist));</span><br><span class="line"> <span class="built_in">queue</span><<span class="keyword">int</span>> q;</span><br><span class="line"> <span class="keyword">while</span> (m--) {</span><br><span class="line"> <span class="keyword">int</span> a, b, c;</span><br><span class="line"> <span class="built_in">cin</span> >> a >> b >> c;</span><br><span class="line"> add(a, b, c);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i <= n; i++) {</span><br><span class="line"> <span class="comment">// set all the point as start point</span></span><br><span class="line"> q.push(i);</span><br><span class="line"> st[i] = <span class="literal">true</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">// BFS</span></span><br><span class="line"> <span class="keyword">while</span>(q.size() && flag) {</span><br><span class="line"> <span class="keyword">int</span> cur = q.front();</span><br><span class="line"> q.pop();</span><br><span class="line"> st[cur] = <span class="literal">false</span>;</span><br><span class="line"> <span class="comment">// update all the adjacent point</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = h[cur]; i != <span class="number">-1</span>; i = ne[i]) {</span><br><span class="line"> <span class="keyword">int</span> j = e[i];</span><br><span class="line"> <span class="keyword">if</span> (dist[j] > dist[cur] + w[i]) {</span><br><span class="line"> dist[j] = dist[cur] + w[i];</span><br><span class="line"> <span class="comment">// update the length of the edge</span></span><br><span class="line"> cnt[j] = cnt[cur] + <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">if</span> (cnt[j] >= n) {</span><br><span class="line"> flag = <span class="literal">false</span>;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">// if marked, then no need to push</span></span><br><span class="line"> <span class="keyword">if</span> (!st[j]) {</span><br><span class="line"> st[j] = <span class="literal">true</span>;</span><br><span class="line"> q.push(j);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (!flag) <span class="built_in">cout</span> << <span class="string">"Yes"</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">cout</span> << <span class="string">"No"</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</li>
</ul>
<h3 id="Floyd-算法（多源最短路）"><a href="#Floyd-算法（多源最短路）" class="headerlink" title="Floyd 算法（多源最短路）"></a>Floyd 算法（多源最短路）</h3><ul>
<li><p><strong>思想：</strong>邻接矩阵存图的距离（不再需要dist数组），自身距离初始化为0，其余距离初始化为正无穷，算法的核心为不断利用中间点更新源点与汇点之间的最短距离，实现方式为三层循环，最外一层循环为中间点，两层内层循环分别为源点和汇点。</p>
</li>
<li><p><span class="exturl" data-url="aHR0cHM6Ly93d3cuYWN3aW5nLmNvbS9wcm9ibGVtL2NvbnRlbnQvODU2Lw==">例题：Floyd求最短路<i class="fa fa-external-link-alt"></i></span></p>
<p><strong>邻接矩阵版本（复杂度：O(N <em> N </em> N)）</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">205</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> INF = <span class="number">0x3f3f3f3f</span>;</span><br><span class="line"><span class="keyword">int</span> g[N][N];</span><br><span class="line"><span class="keyword">int</span> dist[N][N];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> n, m, k;</span><br><span class="line"> <span class="built_in">cin</span> >> n >> m >> k;</span><br><span class="line"> <span class="comment">// initialize the adjacent matrix</span></span><br><span class="line"> <span class="built_in">memset</span>(g, <span class="number">0x3f</span>, <span class="keyword">sizeof</span>(g));</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i <= n; i++) {</span><br><span class="line"> g[i][i] = <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">// read the edge and keep the min edge</span></span><br><span class="line"> <span class="keyword">while</span> (m--) {</span><br><span class="line"> <span class="keyword">int</span> a, b, c;</span><br><span class="line"> <span class="built_in">cin</span> >> a >> b >> c;</span><br><span class="line"> g[a][b] = min(g[a][b], c);</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">// floyd</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> k = <span class="number">1</span>; k <= n; k++)</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i <= n; i++)</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j <= n; j++)</span><br><span class="line"> g[i][j] = min(g[i][j], g[i][k] + g[k][j]);</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">while</span> (k--) {</span><br><span class="line"> <span class="keyword">int</span> x, y;</span><br><span class="line"> <span class="built_in">cin</span> >> x >> y;</span><br><span class="line"> <span class="keyword">if</span> (g[x][y] > INF / <span class="number">2</span>) <span class="built_in">cout</span> << <span class="string">"impossible"</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">cout</span> << g[x][y] << <span class="built_in">endl</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</li>
</ul>
<h2 id="最小生成树算法"><a href="#最小生成树算法" class="headerlink" title="最小生成树算法"></a>最小生成树算法</h2><h3 id="Prim-算法（找最近点，适合点较少的稠密图）"><a href="#Prim-算法（找最近点，适合点较少的稠密图）" class="headerlink" title="Prim 算法（找最近点，适合点较少的稠密图）"></a>Prim 算法（找最近点，适合点较少的稠密图）</h3><ul>
<li><p><strong>思想：</strong>邻接矩阵存图，维持一个连通分量，与 dijkstra 算法类似，每次找到与该连通分量最近的点（dijkstra是找与源点最近的点），将其加入连通分量中，累加其距离，并借助该点更新其他点与连通分量的距离。循环该过程 n 次后，即找到当前的最小生成树。</p>
</li>
<li><p><span class="exturl" data-url="aHR0cHM6Ly93d3cuYWN3aW5nLmNvbS9wcm9ibGVtL2NvbnRlbnQvODYwLw==">例题：Prim算法求最短生成树<i class="fa fa-external-link-alt"></i></span></p>
<p><strong>邻接表版本（复杂度：O(N * N)）</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">505</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> INF = <span class="number">0x3f3f3f3f</span>;</span><br><span class="line"><span class="keyword">int</span> g[N][N];</span><br><span class="line"><span class="keyword">int</span> dist[N];</span><br><span class="line"><span class="keyword">bool</span> st[N];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> n, m;</span><br><span class="line"> <span class="built_in">cin</span> >> n >> m;</span><br><span class="line"> <span class="comment">// initialize the matrix</span></span><br><span class="line"> <span class="built_in">memset</span>(g, <span class="number">0x3f</span>, <span class="keyword">sizeof</span>(g));</span><br><span class="line"> <span class="built_in">memset</span>(dist, <span class="number">0x3f</span>, <span class="keyword">sizeof</span>(dist));</span><br><span class="line"> <span class="built_in">memset</span>(st, <span class="number">0</span>, <span class="keyword">sizeof</span>(st));</span><br><span class="line"> <span class="comment">// read the edge and remove the repeated edege</span></span><br><span class="line"> <span class="keyword">while</span> (m--) {</span><br><span class="line"> <span class="keyword">int</span> a, b, c;</span><br><span class="line"> <span class="built_in">cin</span> >> a >> b >> c;</span><br><span class="line"> g[a][b] = g[b][a] = min(g[a][b], c);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">int</span> res = <span class="number">0</span>;</span><br><span class="line"> <span class="comment">// iterate n times and add the new point</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < n; i++) {</span><br><span class="line"> <span class="keyword">int</span> t = <span class="number">-1</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j <= n; j++) {</span><br><span class="line"> <span class="keyword">if</span> (!st[j] && (t == <span class="number">-1</span> || dist[j] < dist[t]))</span><br><span class="line"> t = j;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (i && dist[t] == INF) {</span><br><span class="line"> res = INF;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> </span><br><span class="line"> <span class="comment">// calculate the distance and mark visited </span></span><br><span class="line"> <span class="keyword">if</span> (i) res += dist[t];</span><br><span class="line"> st[t] = <span class="literal">true</span>;</span><br><span class="line"> </span><br><span class="line"> <span class="comment">// update the distance of the other points</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j <= n; j++) {</span><br><span class="line"> <span class="keyword">if</span> (!st[j] && dist[j] > g[t][j]) {</span><br><span class="line"> dist[j] = g[t][j];</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (res > INF / <span class="number">2</span>) <span class="built_in">cout</span> << <span class="string">"impossible"</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">cout</span> << res << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</li>
</ul>
<h3 id="Kruskal-算法（找最短边，适合点较多的稀疏图）"><a href="#Kruskal-算法（找最短边，适合点较多的稀疏图）" class="headerlink" title="Kruskal 算法（找最短边，适合点较多的稀疏图）"></a>Kruskal 算法（找最短边，适合点较多的稀疏图）</h3><ul>
<li><p><strong>思想：</strong>边结构体存图，并查集存顶点。首先按照边的距离排序后遍历所有边，每次获取边的两个顶点，如果两个顶点不在同一连通分量，则合并，并将该边加入最小生成树，如果最后加入边的距离不等于 n - 1，则代表当前图没有最小生成树。</p>
</li>
<li><p><span class="exturl" data-url="aHR0cHM6Ly93d3cuYWN3aW5nLmNvbS9wcm9ibGVtL2NvbnRlbnQvODYxLw==">例题：Kruskal算法求最小生成树<i class="fa fa-external-link-alt"></i></span></p>
<p><strong>邻接矩阵版本（复杂度：O(MlogM)）</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">1e5</span> + <span class="number">5</span>, M = <span class="number">2e5</span> + <span class="number">5</span>;</span><br><span class="line"><span class="keyword">int</span> p[N];</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">edge</span> {</span></span><br><span class="line"> <span class="keyword">int</span> a, b, c;</span><br><span class="line">}edges[M];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">cmp</span> <span class="params">(edge ea, edge eb)</span> </span>{</span><br><span class="line"> <span class="keyword">return</span> ea.c < eb.c;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> x)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (p[x] != x) p[x] = find(p[x]);</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">return</span> x;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> n, m;</span><br><span class="line"> <span class="built_in">cin</span> >> n >> m;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < m; i++) {</span><br><span class="line"> <span class="keyword">int</span> a, b, c;</span><br><span class="line"> <span class="built_in">cin</span> >> a >> b >> c;</span><br><span class="line"> edges[i] = {a, b, c};</span><br><span class="line"> }</span><br><span class="line"> sort(edges, edges + m, cmp);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i <= n; i++) p[i] = i;</span><br><span class="line"> <span class="keyword">int</span> res = <span class="number">0</span>, cnt = <span class="number">0</span>;</span><br><span class="line"> <span class="comment">// iterate all the edges and merge the new point to the set</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < m; i++) {</span><br><span class="line"> <span class="keyword">auto</span> e = edges[i];</span><br><span class="line"> <span class="keyword">int</span> a = e.a, b = e.b, c = e.c;</span><br><span class="line"> a = find(a), b = find(b);</span><br><span class="line"> <span class="keyword">if</span> (a != b) {</span><br><span class="line"> p[a] = b;</span><br><span class="line"> res += c;</span><br><span class="line"> <span class="comment">// calculate the current size of edges</span></span><br><span class="line"> cnt++;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (cnt != n - <span class="number">1</span>) <span class="built_in">cout</span> << <span class="string">"impossible"</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">cout</span> << res << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</li>
</ul>
<h2 id="二分图算法"><a href="#二分图算法" class="headerlink" title="二分图算法"></a>二分图算法</h2><h3 id="染色法判定二分图（DFS）"><a href="#染色法判定二分图（DFS）" class="headerlink" title="染色法判定二分图（DFS）"></a>染色法判定二分图（DFS）</h3><ul>
<li><p><strong>思想：</strong>邻接表存图，采用DFS遍历所有与当前点相连的点，如相连点未被标记（未标记为0，其余两个颜色为1和2），则标记为不同的颜色，若已标记，则判断颜色是否相等，相等则返回false。</p>
</li>
<li><p><span class="exturl" data-url="aHR0cHM6Ly93d3cuYWN3aW5nLmNvbS9wcm9ibGVtL2NvbnRlbnQvODYyLw==">例题：染色法判定二分图<i class="fa fa-external-link-alt"></i></span></p>
<p><strong>邻接表版本（复杂度：O(M * N)）</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">1e5</span> + <span class="number">10</span>, M = <span class="number">2</span> * N;</span><br><span class="line"><span class="keyword">int</span> h[N], e[M], ne[M], idx = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">int</span> st[N];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b)</span> </span>{</span><br><span class="line"> e[idx] = b, ne[idx] = h[a], h[a] = idx++;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">// dfs</span></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> u, <span class="keyword">int</span> color)</span> </span>{</span><br><span class="line"> st[u] = color;</span><br><span class="line"> <span class="comment">// iterate all the adjacent point</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = h[u]; i != <span class="number">-1</span>; i = ne[i]) {</span><br><span class="line"> <span class="keyword">int</span> j = e[i];</span><br><span class="line"> <span class="comment">// if not visited, give it another color</span></span><br><span class="line"> <span class="keyword">if</span> (!st[j]) {</span><br><span class="line"> <span class="keyword">if</span> (!dfs(j, <span class="number">3</span> - color)) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">// if visited, judge the color</span></span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span> (st[j] == color) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> n, m;</span><br><span class="line"> <span class="built_in">cin</span> >> n >> m;</span><br><span class="line"> <span class="built_in">memset</span>(h, <span class="number">-1</span>, <span class="keyword">sizeof</span>(h));</span><br><span class="line"> <span class="keyword">bool</span> flag = <span class="literal">true</span>;</span><br><span class="line"> <span class="keyword">while</span> (m--) {</span><br><span class="line"> <span class="keyword">int</span> a, b;</span><br><span class="line"> <span class="built_in">cin</span> >> a >> b;</span><br><span class="line"> add(a, b);</span><br><span class="line"> add(b, a);</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">// iterate all the points</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i <= n; i++) {</span><br><span class="line"> <span class="keyword">if</span> (!st[i]) {</span><br><span class="line"> <span class="keyword">if</span> (!dfs(i, <span class="number">1</span>)) {</span><br><span class="line"> flag = <span class="literal">false</span>;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (flag) <span class="built_in">cout</span> << <span class="string">"Yes"</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">cout</span> << <span class="string">"No"</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</li>
</ul>
<h3 id="染色法判定二分图（BFS）"><a href="#染色法判定二分图（BFS）" class="headerlink" title="染色法判定二分图（BFS）"></a>染色法判定二分图（BFS）</h3><ul>
<li><p><strong>思想：</strong>邻接表存图，采用BFS从起点开始访问，同时查询所有与当前点相连的点，如相连点未被标记（未标记为0，其余两个颜色为1和2），则标记为不同的颜色，若已标记，则判断颜色是否相等，相等则返回false。</p>
</li>
<li><p><span class="exturl" data-url="aHR0cHM6Ly93d3cuYWN3aW5nLmNvbS9wcm9ibGVtL2NvbnRlbnQvODYyLw==">例题：染色法判定二分图<i class="fa fa-external-link-alt"></i></span></p>
<p><strong>邻接表版本（复杂度：O(M * N)）</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">typedef</span> pair<<span class="keyword">int</span>, <span class="keyword">int</span>> PII;</span><br><span class="line"><span class="keyword">int</span> n, m;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">1e5</span> + <span class="number">5</span>, M = <span class="number">2e5</span> + <span class="number">5</span>;</span><br><span class="line"><span class="keyword">int</span> h[N], e[M], ne[M], idx = <span class="number">0</span>;</span><br><span class="line">PII q[N];</span><br><span class="line"><span class="keyword">int</span> st[N];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b)</span> </span>{</span><br><span class="line"> e[idx] = b, ne[idx] = h[a], h[a] = idx++;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">bfs</span><span class="params">(<span class="keyword">int</span> u)</span> </span>{</span><br><span class="line"> <span class="comment">// add the start point</span></span><br><span class="line"> <span class="keyword">int</span> hh = <span class="number">0</span>, tt = <span class="number">-1</span>;</span><br><span class="line"> q[++tt] = {u, <span class="number">1</span>};</span><br><span class="line"> st[u] = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">while</span> (hh <= tt) {</span><br><span class="line"> <span class="keyword">auto</span> t = q[hh++];</span><br><span class="line"> <span class="keyword">int</span> cur = t.first, c = t.second;</span><br><span class="line"> <span class="comment">// iterate all the adjacent points</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = h[cur]; i != <span class="number">-1</span>; i = ne[i]) {</span><br><span class="line"> <span class="keyword">int</span> j = e[i];</span><br><span class="line"> <span class="comment">// if not visited, give it another color</span></span><br><span class="line"> <span class="keyword">if</span> (!st[j]) {</span><br><span class="line"> st[j] = <span class="number">3</span> - c;</span><br><span class="line"> q[++tt] = {j, <span class="number">3</span> - c};</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">// if visited, judge the color duplicate or not</span></span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span> (st[j] == c) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">cin</span> >> n >> m;</span><br><span class="line"></span><br><span class="line"> <span class="built_in">memset</span>(h, <span class="number">-1</span>, <span class="keyword">sizeof</span> h);</span><br><span class="line"></span><br><span class="line"> <span class="keyword">while</span> (m -- )</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">int</span> a, b;</span><br><span class="line"> <span class="built_in">cin</span> >> a >> b;</span><br><span class="line"> add(a, b), add(b, a);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">bool</span> flag = <span class="literal">true</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i <= n; i ++ )</span><br><span class="line"> <span class="keyword">if</span> (!st[i])</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (!bfs(i))</span><br><span class="line"> {</span><br><span class="line"> flag = <span class="literal">false</span>;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span> (flag) <span class="built_in">cout</span> << <span class="string">"Yes"</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">cout</span> << <span class="string">"No"</span> << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</li>
</ul>
<h3 id="匈牙利算法求最大匹配"><a href="#匈牙利算法求最大匹配" class="headerlink" title="匈牙利算法求最大匹配"></a>匈牙利算法求最大匹配</h3><ul>
<li><p><strong>思想：</strong>邻接表存图，遍历第一部分的点，统计最大匹配数。统计的过程为遍历第二部分的点，找到所有相邻点，并尝试与第一部分当前正在遍历的点进行匹配，如果第二部分的点未被匹配或者匹配的第一部分点可以找到其他类型的匹配，则<strong>优先匹配当前这一对</strong>。</p>
</li>
<li><p><span class="exturl" data-url="aHR0cHM6Ly93d3cuYWN3aW5nLmNvbS9wcm9ibGVtL2NvbnRlbnQvODYzLw==">例题：二分图的最大匹配<i class="fa fa-external-link-alt"></i></span></p>
<p><strong>邻接表版本（复杂度：O(MN)）</strong></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">505</span>, M = <span class="number">1e5</span> + <span class="number">5</span>;</span><br><span class="line"><span class="keyword">int</span> h[N], e[M], ne[M], idx = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">int</span> match[N];</span><br><span class="line"><span class="keyword">bool</span> st[N];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b)</span> </span>{</span><br><span class="line"> e[idx] = b, ne[idx] = h[a], h[a] = idx++;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="comment">// find the couple</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> x)</span> </span>{</span><br><span class="line"> <span class="comment">// find all the possible match</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = h[x]; i != <span class="number">-1</span>; i = ne[i]) {</span><br><span class="line"> <span class="keyword">int</span> j = e[i];</span><br><span class="line"> <span class="comment">// if not visited</span></span><br><span class="line"> <span class="keyword">if</span> (!st[j]) {</span><br><span class="line"> <span class="comment">// mark visited</span></span><br><span class="line"> st[j] = <span class="literal">true</span>;</span><br><span class="line"> <span class="comment">// if not match or if we can find a new couple</span></span><br><span class="line"> <span class="comment">// match it</span></span><br><span class="line"> <span class="keyword">if</span> (match[j] == <span class="number">0</span> || find(match[j])) {</span><br><span class="line"> match[j] = x;</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> n1, n2, m;</span><br><span class="line"> <span class="built_in">cin</span> >> n1 >> n2 >> m;</span><br><span class="line"> <span class="built_in">memset</span>(h, <span class="number">-1</span>, <span class="keyword">sizeof</span>(h));</span><br><span class="line"> <span class="keyword">while</span> (m--) {</span><br><span class="line"> <span class="keyword">int</span> a, b;</span><br><span class="line"> <span class="built_in">cin</span> >> a >> b;</span><br><span class="line"> add(a, b);</span><br><span class="line"> }</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">int</span> res = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i <= n1; i++) {</span><br><span class="line"> <span class="comment">// clear the state and find some new couples</span></span><br><span class="line"> <span class="built_in">memset</span>(st, <span class="literal">false</span>, <span class="keyword">sizeof</span>(st));</span><br><span class="line"> <span class="keyword">if</span> (find(i)) res++;</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">cout</span> << res << <span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></li>
</ul>
</div>
<footer class="post-footer">
<div class="post-tags">
<a href="/tags/Notes/" rel="tag"># Notes</a>
<a href="/tags/Algorithm/" rel="tag"># Algorithm</a>
<a href="/tags/Data-Structrue/" rel="tag"># Data Structrue</a>
<a href="/tags/Graph-theory/" rel="tag"># Graph theory</a>
</div>
<div class="post-nav">
<div class="post-nav-item">
<a href="/baoyan-experience.html" rel="prev" title="2021计算机保研面试经验与建议（中山、复旦、北航、浙大工程师、华东师、华工等院校）">
<i class="fa fa-chevron-left"></i> 2021计算机保研面试经验与建议（中山、复旦、北航、浙大工程师、华东师、华工等院校）
</a></div>
<div class="post-nav-item">
<a href="/ginTodoList.html" rel="next" title="ginTodoList——基于gin和gorm的待办小清单">
ginTodoList——基于gin和gorm的待办小清单 <i class="fa fa-chevron-right"></i>
</a></div>
</div>
</footer>
</article>
</div>
<div class="comments" id="valine-comments"></div>
<script>
window.addEventListener('tabs:register', () => {
let { activeClass } = CONFIG.comments;
if (CONFIG.comments.storage) {
activeClass = localStorage.getItem('comments_active') || activeClass;
}
if (activeClass) {
let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
if (activeTab) {
activeTab.click();
}
}
});
if (CONFIG.comments.storage) {
window.addEventListener('tabs:click', event => {
if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
let commentClass = event.target.classList[1];
localStorage.setItem('comments_active', commentClass);
});
}
</script>
</div>
<div class="toggle sidebar-toggle">
<span class="toggle-line toggle-line-first"></span>
<span class="toggle-line toggle-line-middle"></span>
<span class="toggle-line toggle-line-last"></span>
</div>
<aside class="sidebar">
<div class="sidebar-inner">
<ul class="sidebar-nav motion-element">
<li class="sidebar-nav-toc">
文章目录
</li>
<li class="sidebar-nav-overview">
站点概览
</li>
</ul>
<!--noindex-->
<div class="post-toc-wrap sidebar-panel">
<div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#前言"><span class="nav-number">1.</span> <span class="nav-text">前言</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#树的存储和图的存储"><span class="nav-number">2.</span> <span class="nav-text">树的存储和图的存储</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#树与图的搜索"><span class="nav-number">3.</span> <span class="nav-text">树与图的搜索</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#拓扑排序"><span class="nav-number">4.</span> <span class="nav-text">拓扑排序</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#最短路算法"><span class="nav-number">5.</span> <span class="nav-text">最短路算法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#Dijkstra-算法（单源最短路）"><span class="nav-number">5.1.</span> <span class="nav-text">Dijkstra 算法（单源最短路）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Bellman-ford-算法（单源最短路）"><span class="nav-number">5.2.</span> <span class="nav-text">Bellman-ford 算法（单源最短路）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#SPFA-算法（单源最短路）"><span class="nav-number">5.3.</span> <span class="nav-text">SPFA 算法（单源最短路）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#SPFA-算法（判断负环）"><span class="nav-number">5.4.</span> <span class="nav-text">SPFA 算法（判断负环）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Floyd-算法（多源最短路）"><span class="nav-number">5.5.</span> <span class="nav-text">Floyd 算法（多源最短路）</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#最小生成树算法"><span class="nav-number">6.</span> <span class="nav-text">最小生成树算法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#Prim-算法（找最近点，适合点较少的稠密图）"><span class="nav-number">6.1.</span> <span class="nav-text">Prim 算法（找最近点，适合点较少的稠密图）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Kruskal-算法（找最短边，适合点较多的稀疏图）"><span class="nav-number">6.2.</span> <span class="nav-text">Kruskal 算法（找最短边，适合点较多的稀疏图）</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#二分图算法"><span class="nav-number">7.</span> <span class="nav-text">二分图算法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#染色法判定二分图（DFS）"><span class="nav-number">7.1.</span> <span class="nav-text">染色法判定二分图（DFS）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#染色法判定二分图（BFS）"><span class="nav-number">7.2.</span> <span class="nav-text">染色法判定二分图（BFS）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#匈牙利算法求最大匹配"><span class="nav-number">7.3.</span> <span class="nav-text">匈牙利算法求最大匹配</span></a></li></ol></li></ol></div>
</div>
<!--/noindex-->
<div class="site-overview-wrap sidebar-panel">
<div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
<p class="site-author-name" itemprop="name">Charfole</p>
<div class="site-description" itemprop="description">Carpe diem</div>
</div>
<div class="site-state-wrap motion-element">
<nav class="site-state">
<div class="site-state-item site-state-posts">
<a href="/archives/">
<span class="site-state-item-count">14</span>
<span class="site-state-item-name">日志</span>
</a>
</div>
<div class="site-state-item site-state-categories">
<a href="/categories/">
<span class="site-state-item-count">8</span>
<span class="site-state-item-name">分类</span></a>
</div>
<div class="site-state-item site-state-tags">
<a href="/tags/">
<span class="site-state-item-count">29</span>
<span class="site-state-item-name">标签</span></a>
</div>
</nav>
</div>
<div class="links-of-author motion-element">
<span class="links-of-author-item">
<span class="exturl" data-url="aHR0cHM6Ly9naXRodWIuY29tL2NoYXJmb2xl" title="GitHub → https://github.com/charfole"><i class="fab fa-github fa-fw"></i>GitHub</span>
</span>
<span class="links-of-author-item">
<span class="exturl" data-url="bWFpbHRvOmNoYXJmb2xlQDE2My5jb20=" title="E-Mail → mailto:[email protected]"><i class="fa fa-envelope fa-fw"></i>E-Mail</span>
</span>
<span class="links-of-author-item">
<a href="/atom.xml" title="RSS → /atom.xml"><i class="fa fa-rss fa-fw"></i>RSS</a>
</span>
</div>
<div class="cc-license motion-element" itemprop="license">
<span class="exturl cc-opacity" data-url="aHR0cHM6Ly9jcmVhdGl2ZWNvbW1vbnMub3JnL2xpY2Vuc2VzL2J5LW5jLXNhLzQuMC8="><img src="/images/cc-by-nc-sa.svg" alt="Creative Commons"></span>
</div>
</div>
<div class="back-to-top motion-element">
<i class="fa fa-arrow-up"></i>
<span>0%</span>
</div>
</div>
</aside>
<div id="sidebar-dimmer"></div>
</div>
</main>
<footer class="footer">
<div class="footer-inner">
<div class="copyright">
© 2020 –
<span itemprop="copyrightYear">2023</span>
<span class="with-love">
<i class="fa fa-heart"></i>
</span>
<span class="author" itemprop="copyrightHolder">Charfole</span>
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-chart-area"></i>
</span>
<span class="post-meta-item-text">站点总字数：</span>
<span title="站点总字数">61k</span>
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-coffee"></i>
</span>
<span class="post-meta-item-text">站点阅读时长 ≈</span>
<span title="站点阅读时长">55 分钟</span>
</div>
<div class="powered-by">由 <span class="exturl theme-link" data-url="aHR0cHM6Ly9oZXhvLmlv">Hexo</span> & <span class="exturl theme-link" data-url="aHR0cHM6Ly90aGVtZS1uZXh0Lm9yZw==">NexT.Gemini</span> 强力驱动
</div>
<div class="busuanzi-count">
<script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
<span class="post-meta-item" id="busuanzi_container_site_uv" style="display: none;">
<span class="post-meta-item-icon">
<i class="fa fa-user"></i>
</span>
<span class="site-uv" title="总访客量">
<span id="busuanzi_value_site_uv"></span>
</span>
</span>
<span class="post-meta-divider">|</span>
<span class="post-meta-item" id="busuanzi_container_site_pv" style="display: none;">
<span class="post-meta-item-icon">
<i class="fa fa-eye"></i>
</span>
<span class="site-pv" title="总访问量">
<span id="busuanzi_value_site_pv"></span>
</span>
</span>
</div>
</div>
</footer>
</div>
<script src="/lib/anime.min.js"></script>
<script src="/lib/velocity/velocity.min.js"></script>
<script src="/lib/velocity/velocity.ui.min.js"></script>
<script src="/js/utils.js"></script>
<script src="/js/motion.js"></script>
<script src="/js/schemes/pisces.js"></script>
<script src="/js/next-boot.js"></script>
<script>
(function(){
var canonicalURL, curProtocol;
//Get the <link> tag
var x=document.getElementsByTagName("link");
//Find the last canonical URL
if(x.length > 0){
for (i=0;i<x.length;i++){
if(x[i].rel.toLowerCase() == 'canonical' && x[i].href){
canonicalURL=x[i].href;
}
}
}
//Get protocol
if (!canonicalURL){
curProtocol = window.location.protocol.split(':')[0];
}
else{
curProtocol = canonicalURL.split(':')[0];
}
//Get current URL if the canonical URL does not exist
if (!canonicalURL) canonicalURL = window.location.href;
//Assign script content. Replace current URL with the canonical URL
!function(){var e=/([http|https]:\/\/[a-zA-Z0-9\_\.]+\.baidu\.com)/gi,r=canonicalURL,t=document.referrer;if(!e.test(r)){var n=(String(curProtocol).toLowerCase() === 'https')?"https://sp0.baidu.com/9_Q4simg2RQJ8t7jm9iCKT-xh_/s.gif":"//api.share.baidu.com/s.gif";t?(n+="?r="+encodeURIComponent(document.referrer),r&&(n+="&l="+r)):r&&(n+="?l="+r);var i=new Image;i.src=n}}(window);})();
</script>
<script src="/js/local-search.js"></script>
<script>
if (typeof MathJax === 'undefined') {
window.MathJax = {
loader: {
source: {
'[tex]/amsCd': '[tex]/amscd',
'[tex]/AMScd': '[tex]/amscd'
}
},
tex: {
inlineMath: {'[+]': [['$', '$']]},
tags: 'ams'
},
options: {
renderActions: {
findScript: [10, doc => {
document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
const display = !!node.type.match(/; *mode=display/);
const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
const text = document.createTextNode('');
node.parentNode.replaceChild(text, node);
math.start = {node: text, delim: '', n: 0};
math.end = {node: text, delim: '', n: 0};
doc.math.push(math);
});
}, '', false],
insertedScript: [200, () => {
document.querySelectorAll('mjx-container').forEach(node => {
let target = node.parentNode;
if (target.nodeName.toLowerCase() === 'li') {
target.parentNode.classList.add('has-jax');
}
});
}, '', false]
}
}
};
(function () {
var script = document.createElement('script');
script.src = '//cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js';
script.defer = true;
document.head.appendChild(script);
})();
} else {
MathJax.startup.document.state(0);
MathJax.texReset();
MathJax.typeset();
}
</script>
<script>
NexT.utils.loadComments(document.querySelector('#valine-comments'), () => {
NexT.utils.getScript('//unpkg.com/valine/dist/Valine.min.js', () => {
var GUEST = ['nick', 'mail', 'link'];
var guest = 'nick,mail,link';
guest = guest.split(',').filter(item => {
return GUEST.includes(item);
});
new Valine({
el : '#valine-comments',
verify : false,
notify : false,
appId : 'hXI9oKO1Olitf9gLi5jb1ciq-gzGzoHsz',
appKey : 'JrOSBT9CBoGf3OzREeMchSkt',
placeholder: "Just go go",
avatar : 'mm',
meta : guest,
pageSize : '10' || 10,
visitor : false,
lang : '' || 'zh-cn',
path : location.pathname,
recordIP : false,
serverURLs : ''
});
}, window.Valine);
});
</script>
</body>
</html>