Feng003
Feng003
全部文章
图论
codeforces(2)
DP(3)
基础数据结构(2)
字符串(1)
数据结构课程(1)
概率期望(1)
算法课课程作业(4)
题解(6)
归档
标签
去牛客网
登录
/
注册
Feng003的博客
一些***的玩意
全部文章
/ 图论
(共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
431