回归梦想

题解

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2)

/ 注册

全部文章 / 题解（共12篇）

NC20099 [HNOI2012]矿场搭建来自专栏

NC20099 [HNOI2012]矿场搭建题目： • 煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。• 于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。•...

**** tarjan 割点

2021-01-14

0 758

NC51307 Redundant Paths

NC51307 Redundant Paths 题目： • 给定无向连通图，求至少需要添加几条边使它变成一个边双连通图。（添多少边可以消灭所有的桥）题解：先用边双连通缩点• 缩点之后是一棵树• 无根树的叶子（度数为1的点）都需要再添一条边，叶子节点两两连接• 答案是是（叶子数+1）/2 代码：...

** tarjan 缩点

2021-01-14

0 535

NC106972 Cow Ski Area

NC106972 Cow Ski Area 题目： • N*M的滑雪场，每个点都有他的高度，滑雪的时候只能向四周相邻的不高于当前点的高度的点滑，现在滑雪场准备修建若干个缆车线路，使得奶牛可以从任意一个点运动到滑雪场的每个点，问最少需要建多少条缆车线路。题解：本质还是有向图，通过加边使其强连通• ...

** tarjan 缩点

2021-01-14

0 586

NC51269 Network of Schools

NC51269 Network of Schools 题目：给你一张有向图，问最少要加几条边才能使得图上的点都属于同一个强连通分量题解：加边变成强连通分量缩点之后，入度为0的点和出度为0的点两两连边，多随便一连——答案就是max（入度为0的点数，出度为0的点数）处理后：代码： #inclu...

** tarjan 缩点

2021-01-14

0 645

NC50403 [ZJOI2004]嗅探器

NC50403 嗅探器题目： • 某军搞信息对抗实战演习，红军成功地侵入了蓝军的内部网络，蓝军共有两个信息中心，红军计划在某台中间服务器上安装一个嗅探器，从而能够侦听到两个信息中心互相交换的所有信息，但是蓝军的网络相当的庞大，数据包从一个信息中心传到另一个信息中心可以不止有一条通路。现在需要你尽快...

*** tarjan 割点

2021-01-14

1 803

NC20603 [ZJOI2007]最大半连通子图

NC20603 [ZJOI2007]最大半连通子图题目： • 一个有向图G=(V,E)称为半连通的(Semi-Connected)，如果满足：u,v∈V，满足u→v或v→u，即对于图中任意两点u，v,存在一条u到v的有向路径或者从v到u的有向路径。• 若G'=(V',E')满足V'∈V，E'是E...

拓扑排序 **** tarjan 缩点

2021-01-14

0 735

可达性

来源：牛客网 @[toc] 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld 题目描述给出一个 0 ≤ N ≤ 105 点数、0 ≤ M ≤ 105 边数的有向图，输出一个尽可能小的点集，使得从这些...

tarjan

2020-06-22

4 789

Caocao's Bridges HDU - 4738

Caocao's Bridges HDU - 4738@[toc] 题目： Caocao was defeated by Zhuge Liang and Zhou Yu in the battle of Chibi. But he wouldn't give up. Caocao's army st...

tarjan

2020-06-22

0 816

HDU4612 Warm up

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others) Total Submission(s): 11184 Accepted Submission(s): 2573 HDU461...

树的直径 tarjan

2020-06-21

0 584

POJ3177 Redundant Paths

POJ3177 Redundant Paths@[toc] Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 21945 Accepted: 9056 Description In order to g...

tarjan

2020-06-21

0 461