whix

图论

acm(1) codeforces(13) dp(1) java(1) 区域赛真题(2) 字符串(3) 数据结构(4) 数论(37) 未归档(32) 牛客(8) 组合数学(7) 计算几何(1) 题解(9)

/ 注册

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

Is-A? Has-A? Who Knowz-A?【传递闭包】

题目： Two familiar concepts in object oriented programming are the is-a and has-a relationships. Given two classes A and B, we say that A is-a B if A i...

2020-03-01

0 395

0 or 1 HDU - 4370【最短路+起点的最小环】

分析：把所给矩阵当作邻接矩阵，由三个限制，可以得到： 1.节点 1 1 1 的出度为 ...

2020-02-27

0 382

Path HDU - 6582【求最短路所有边+最小割】

题意：给一个有向图，删除每一条边的代价是边的长度，要求花费最小的代价，使得 1 → n ...

2020-02-20

0 398

CodeForce 1304E 1-Trees and Queries【LCA】

题意：首先给一棵 n n n 个点的树，然后有 q ...

2020-02-16

0 239

Roadblocks POJ - 3255【次最短路】

求到某个点 v v v 的次最短路，可认为是到某点 u ...

2020-02-10

0 407

树上差分

1.点差分：求解问题：给一棵树，和一些路径的起点和终点，求树上的每个点被路径经过的次数。求解步骤： 1.假设路径的起点： s s ...

2020-02-09

0 283

树链剖分及应用

定义：将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。就是一种技巧，为了方便处理问题。形式：重链剖分，长链剖分等。此处讲述重链剖分。重链剖分：可以将树上的任意一条路径划分成不超过 ...

2020-02-06

0 285

树的重心

定义： 1.找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。 2.从树中去掉某点以及和该点相连的所有边后，整棵树变为许多"块"。去掉任意一个重心（相比于去掉其他点）可以使得生成的各个"块"...

2020-02-03

0 460

树的直径及应用

树的直径：树的直径指树上距离最远的两点间的距离，它在树上问题上有许多应用，往往通过树的直径的性质可以将一个高时间复杂度的解法变为线性求解。树的直径的性质： ( 1 ...

2020-02-03

0 347

codeforce 1294F-Three Paths on a Tree【树的直径+多源bfs】

一开始认为根节点和深度最深的节点一定要选择（其实是错的），确定了两个点后枚举第三个点，用倍增求深度最深的点和枚举的点的lca,确定第三个点。正解：用两次 d f ...

2020-02-02

0 262