Feng003

图论

codeforces(2) DP(3) 基础数据结构(2) 字符串(1) 数据结构课程(1) 概率期望(1) 算法课课程作业(4) 题解(6)

/ 注册

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

分层最短路（计蒜客 - A1958 ）

问题：给定一张有n个点，m条有向边的图。一个整数k。（n<=1e5,m<=2e5,k<=10）。你有k次机会使得图中的某一条边权值变为0。求1号点到n号点的最短距离。保证至少存在一条路径从1到n。思路：dijkstra算法+dp转移　　这其实就是一道分层最短路的模板题。普通的d...

dijkstra 分层最短路

2020-04-12

0 570

HYSBZ 2438杀人游戏（tarjan 缩点 + 思维）

理解完题意后，能容易想到答案就是1 - 未知身份人数 / 总人数。所以我们就把问题转换成求一共有几个人是身份是未知的（即他的身份是无法从他人那里获取的）。因为其他人我们可以通过这些人来安全的推导出他的身份。所谓的递推吧... 于是我们把n个人看成图上的n个点，认识关系看成点与点之间的有向边。容...

2020-02-10

0 432