Rewinner

图论

ACM(1) dfsdd(1) DP(6) hash(1) STL(1) 小技巧(4) 思维(6) 搜索(2) 数学(5) 数据结构(16) 未归档(70)

/ 注册

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

Floyd算法(多源最短路)

Floyd 如果你有挑战程序设计竞赛第二版(群文件里面有PDF版本)，你可以看P103讲解的很好。如果要用到 Floyd 算法建边方式基本都是邻接矩阵，因为时间复杂度为O(n^3)，所以说n通常都不会很大。 Floyd 可以求解多源最短路，传递闭包(POJ3660)，求最小环。代码： ...

2019-07-14

0 515

邻接表（链式向前星）

邻接表（链式向前星）链式向前星：用来储存边的信息的以中方法。优点：速度快，节省空间，很常用如果我们用 Vector 来建边，相当于开的是一个动态的二维数组，较数组模拟来说比较慢。有时候还卡空间(被某一道题卡崩的YMF学长：我再用Vector建边我是🐶)。我先把基本代码贴出来。 #...

2019-07-14

0 691

西北大学：西湖奇遇记Ⅰ【最短路】

传送门看代码更容易理解 ///#include<bits/stdc++.h> ///#include<unordered_map> ///#include<unordered_set> #include<iostream> #include&l...

2019-05-12

0 477

Power OJ 2854 小Z的糖果难题【单调栈+倍增】

传送门中文题目就不在阐述题意比赛时我们用分块来解决的，但是T掉了。。。思路：我们使用单调栈维护的每个点可以跳跃到的下一个点，相当于两个点之间可以建一条边（如果不存在下一个点，可以和一个虚拟根结点建边），最后利用倍增求LCA的思想将L，不断向上跳跃，直到不能继续时，当前位置就是最后的位置，两...

2019-04-18

0 447

CodeForces - 1051F 【LCA + 最短路】

传送门大概题意给你一个包含n个点m条无向边的图，多次询问最短路(保证每两个点都连通，m - n ≤ 20 )思路我们要注意题面上给你的条件( m - n ≤ 20 )，这是一个很重要的信息。我们知道含有n个结点的树包含 n - 1 条边，这道题相当于在树上又多加了几条边。如果给我们一棵树，多...

2019-03-30

0 612

POJ 3728 The merchant 【在线LCA+细节】

传送门题意：一个国家有N个城市，每对城市之间只有一条简单的道路。商人选择了一些道路，并希望在每条道路上赚尽可能多的钱。当他沿着一条道路移动时，他可以选择一个城市购买一些商品，然后在一个城市中出售。所有城市的商品都一样，但价格不同。现在，您的任务是计算每条路径上可能的最大利润。解析：这道题...

2019-03-28

0 447

POJ3417 Network【LCA+树上差分】

传送门 Description Yixght is a manager of the company called SzqNetwork(SN). Now she's very worried because she has just received a bad news which deno...

2019-03-28

0 484

图的割点学习+模板题【Tanjan】

什么叫做割点？在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。图中c就是一个割点，剩下{A,B}和{C,D}两个连通分量实现原理：在学习割点的基础上应该了解什么是连通分量和T...

2019-03-22

0 649

【2-SAT初学+模板题讲解】POJ3683 Priest John's Busiest Day

什么是2-SAT? SAT是适定性(Satisfiability)问题的简称。一般形式为k-适定性问题，简称 k-SAT。可以证明，当k>2时，k-SAT是NP完全的。因此一般讨论的是k=2的情况，即2-SAT问题。我们通俗的说，就是给你n个变量ai，每个变量能且只能取0...

2019-03-21

0 635

CodeForces - 744A Hongcow Builds A Nation 【并查集】

传送门 Description|Hongcow is ruler of the world. As ruler of the world, he wants to make it easier for people to travel by road within their own countr...

2019-03-14

0 685