Roads

题目描述： 有一个 \(n\) 个点的图，对于每两个点 \((i,j)\) 之间都有一条长度为 \(w_{i,j}\) 的无向边。 给你一个点 \(t\)，你需要构造一棵以 \(t\) 为根的生成树，使得\(\sum\limits_{i=1}^{n}s(i,t)\) 尽量小。\(s(i,t)\) 为 ......

好经典的题，因为暑假前集训做过类似的思想的题所以知道怎么处理 这题由于要求最多的删去的边数，则等价于求最少保留几条边，很显然留下的边一定是最短路上的 但问题是如果两条路不相交的话很简单，可事实是两条路径可以重叠一些部分，这些边用了两次可能可以使答案变优 关于这种图上两条路径的题有一个经典结论，即两条 ......

首先 \(a\) 边可以随便选。 显然，若某条 \(b\) 边的两端位于同一 \(a\) 连通块，一定不会被我们考虑。剩下的 \(b\) 边一定会将两个 \(a\) 连通块相连。 那么此时我们对于 \(b\) 边的约束是，位于一个环上的 \(b\) 边不能同时存在图中，即，我们的路径不能从当前连通块 ......

洛谷传送门 CF 传送门 考虑一条 \(1 \to i\) 的路径是否在最小生成树上。 称边权为 \(a\) 的边为轻边，边权为 \(b\) 的边为重边。 轻边若不成环则一定在最小生成树上，因此先把轻边合并，这样形成了若干连通块。 那么如果两点在一个连通块，它们只能通过轻边互达。 同时，因为是树上路 ......

1D8 ya。 设 \(f_{u,i}\) 表示覆盖了 \(u\) 子树并且向上覆盖到了深度为 \(i\) 的最小代价。 考虑合并儿子 \(v\): \[f'_{u,i}\gets \min\left(f_{u,i}+\min\limits_{j=1}^nf_{v,j},f_{v,i}+\min\l ......

题意：给出一棵无向树，求树的直径，即树上两点之间的最长距离 分析：两种解法 解法1：先任取一个点，找到距离该点最远的点u，再找到距离u最远的点v，那么u和v之间的路径就是一条直径。 证明：只要找到了树的直径的一个端点，再从该点找到最远点就一定是直径的另一个端点。所以只需要证明第一次找到的最远点u就是 ......

[题目链接](https://www.luogu.com.cn/problem/CF671D) 题目要求我们求出选出若干条路径并最小化花费，如果这是在链上，我们可以考虑直接枚举每条路径的右端点 dp，那树呢？把路径剖分整个覆盖的集合就不一定连续了，没法 dp，况且题目里给了很强的条件：路径一定是从孩 ......

[Blocked Roads](https://www.luogu.com.cn/problem/AT_abc218_f) ### 题目大意 给定一张 $n$ 个点，$m$ 条边的无向图，每条边的边权均为 $1$。对于每一个 $i\in [1,m]$ 求出从点 $1$ 到 $n$ 的不经过第 $i$ ......

## D. Directed Roads  ![img](https://img2023.cnblogs.c ......

P3008 [USACO11JAN]Roads and Planes G ##思路 按照分连通块的方法进行计算，并且如果不是本连通块的点，不能在现在的本次dfs中求解最小值。要一个一个的联通快进行标记。 /* 不能直接走disj的话，缩点的思想很重要 首先尽量不要使用spfa进行走图，可能会卡 对道 ......

题意：有一个旅游区，旅游区有很多的景点，景点间需要开通缆车，使得任意两个景点可以互相到达。现在给出一些点间的缆车线路制造成本，两个景点之间可能有多重制造方式。问最少的花费是多少。 分析：连通+最少的花费 = 最小生成树。 Prim算法适用于稠密图, Kruskal适用于稀疏图 好家伙，两个 runt ......

~~看到 $n\le 70$，想到状压 DP。~~ 首先，显然对于一棵最小生成树，每个轻边连通块内部都是一棵树，轻边连通块缩点后点之间的重边也是一棵树。也就是说，缩点后不存在重边组成的环（包括自环），路径一旦离开了一个轻边连通块就再也不会回来了。 于是先洪水填充求出连通块，设共有 $k$ 个连通块。 ......