an_da

题解

/ 注册

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

树上拓扑序计数

F 较好的观感树上拓扑序计数|树形DP https://ac.nowcoder.com/acm/contest/38630/F 思路每个公司是一棵树，然后每个公司可以看做连在一个虚拟的根上。每个公司的计算方案实际上就是计算这棵树的拓扑序的个数。用树形DP求解。 f[u]f[u]f[u] : 以u...

深度优先搜索

2022-08-20

9 504

题解 | #道路建设#

题解（最小生成树） kruskal 博客链接：https://blog.csdn.net/qq_50285142/article/details/116995428 #include<bits/stdc++.h> using namespace std; typedef long lon...

最小生成树

2021-05-17

0 552

题解 | #[SCOI2005]繁忙的都市#

思路：1.先存储所有的边，包括起点，终点，权值u,v,w2.对所有的边按权值从小到大排序3.最小生成树得到的边数一定是n-1（点的数目减一），按权值从小到大取边，如果选中该边，就把这条边的两个点加入到一个集合（表示有同样的归属关系，就是我们所说的并查集）里面，下次选边时，如果有节点已经在这个集合中，...

最短路

2021-05-17

0 516

题解 | #小木乃伊到我家#

dijkstra解法 1.距离要初始化为inf2.边的存储要弄清存储的方式，以及各自代表的含义；比如说pair存储，first代表边的指向的点，second代表边的权值，而数组的第一维代表边的起点。3.优先队列存储的信息要清楚它的作用：存储距离：目的是对距离进行排序，每次取出距离最小的节点，功能只是...

最短路

2021-05-15

0 625