expect2004
expect2004
全部文章
图论 - 生成树
Codeforces Round(2)
Contests(11)
review(2)
其他(1)
动态规划(19)
动态规划 - 区间DP(3)
动态规划 - 期望与概率DP(1)
动态规划 - 树形DP(4)
动态规划 - 状压DP(1)
动态规划 - 线性DP(1)
动态规划 - 背包(2)
图论 - Tarjan(4)
图论 - 二分图判定(2)
图论 - 拓扑排序(1)
图论 - 最短路(1)
字符串 - AC自动机(2)
字符串 - KMP(2)
字符串 - 后缀数组(SA)(3)
字符串 - 字典树(Trie)(1)
数学 - 其他(2)
数学 - 多项式(3)
数学 - 组合计数(1)
数学 - 莫比乌斯反演(2)
数学 - 高斯消元(2)
数据结构 - 分块(1)
数据结构 - 平衡树(1)
数据结构 - 树状数组(1)
数据结构 - 树链剖分(2)
数据结构 - 珂朵莉树(2)
数据结构 - 线段树(6)
数据结构 - 虚树(1)
未归档(6)
模板(5)
游记(3)
算法 - 2-SAT(2)
算法 - CDQ分治(1)
算法 - 搜索(2)
算法 - 树分治(2)
算法 - 矩阵树定理(1)
网络流(7)
网络流 - 二分图相关(1)
网络流 - 最大流(1)
网络流 - 最小割(6)
题解(22)
归档
标签
去牛客网
登录
/
注册
萌新expect的博客
由零至灵,由壹达意
全部文章
/ 图论 - 生成树
(共3篇)
CF1005F Berland and the Shortest Paths 最短路树计数
问题描述 LG-CF1005F 题解 由题面显然可得,所求即最短路树。 所以跑出最短路树,计数,输出方案即可。 \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; template <t...
2019-11-06
0
463
LG5201 「USACO2019JAN」Shortcut 最短路树
\(\mathrm{Shortcut}\) 问题描述 LG5201 题解 最短路树。 显然奶牛的路径就是从\(1\)走到各个草地,于是从\(1\)跑最短路,构建最短路树。 为了保证字典序,从\(1\)到\(n\)依次枚举每个结点,构建。 显然,用贪心的思想,这条边一定是从某个结点\(x...
2019-09-22
0
638
CF1076D Edge Deletion 最短路树
问题描述 Codeforces 洛谷(有翻译) 题解 最短路树,是一棵在最短路过程中构建的树。 在\(\mathrm{Dijkstra}\)过程中,如果最终点\(y\)是由点\(x\)转移得到的,则在最短路树上\(x\)是\(y\)的父节点,\(x\)到\(y\)的最短路树上长度等于原...
2019-09-11
0
405