T1
• 在 \(N\) 个点 \(P\) 条边的加权无向图上求出一条从 \(1\) 号结点到 \(N\) 号结点的路径，使路径上第 \(K + 1\) 大的边权尽量小。
• \(0 ≤ K < N ≤ 1000\), \(1 ≤ P ≤ 2000\)。
Solution
• 一道自己做出来的蓝。
• 二分第 \(K + 1\) 大边权为 \(mid\)，每次把边权 \(\leq mid\) 的都设为 \(0\)，否则设为 \(1\)。
• 从节点 \(1\) 跑一次最短路，当 \(dist[n] \leq mid\) 时则满足条件，否则不满足。
• 正确性显然。
T2
• 树形黑暗城堡有 \(N\) 个房间，\(M\) 条可以制造的双向通道，以
及每条通道的长度。
• 设 \(D_i\) 为如果所有的通道都被修建，第 \(i\) 号房间与第 \(1\) 号房间的最短路径长度；
• 而 \(S_i\) 为实际修建的树形城堡中第 \(i\) 号房间与第 \(1\) 号房间的路径长度；
• 要求对于所有整数 \(i\) \((1 ≤ i ≤ N)\)，有 \(S_i = D_i\) 成立。
• 有多少种不同的城堡修建方案，答案对 \(2 ^ {31} − 1\) 取模。
Solution
• 简单来说，题目要求最短路径树的数量。
• 最短路径树是网络的源点到所有结点的最短路径构成的树。
• 我们从节点 \(1\) 跑一遍最短路。
• 当 \(dist[v] = dist[u] + e(u, v)\) 时，表明 \(v\) 的最短路是由 \(u\) 得到的，那 \(e(u, v)\) 就可以作为最短路径树上的边。
• 对每个点计算出它可作为最短路径树上的边的数量，根据乘法原理，乘起来就是答案。
T3
• 要给 \(n\) 口矿井供电。
• 为了保证电力的供应，有两种办法：
\(1.\) 在这一口矿井上建立一个发电站，费用为 \(v\)。
\(2.\) 将这口矿井与另外的已经有电力供应的矿井之间建立电网，费用为 \(p\)。
• 计算保证所有矿井电力供应的最小花费。
• \(1 ≤ n ≤ 300\), \(0 ≤ vi, p_{ij} ≤ 10^5\)。
Solution
• 简单来说，要使每个点所在的联通块的都至少有一个发电站的最小花费。
• 建立一个虚拟源点 \(0\)，给每口矿井连一条边权为 \(v_i\) 的边，跑一遍最小生成树即可。
T4
• \(N\) 头牛（每头牛的编号就是它所在农场的编号）要去参加一场在编号为 \(x\) 的牛的农场举行的派对。
• 有 \(M\) 条有向道路，每条路长 \(T_i\)；
• 每头牛都必须参加完派对后回到家，每头牛都会选择最短路径。
• 求这 \(N\) 头牛的最短路径（一个来回）中最长的一条的长度。
• \(1 ≤ N ≤ 1000\)，\(1 ≤ x ≤ N\)。
• \(1 ≤ M ≤ 100000\)，\(1 ≤ T_i ≤ 100\)。
Solution
• 扇贝题目。
• 先跑一遍各点到 \(x\) 的距离，然后再跑一遍 \(x\) 到各点的距离即可。
• 但是朴素做法，虽然可以通过此题，但我们考虑优化。
• 建立正图和反图，都以 \(x\) 为起点，预处理出到每个点的最短路 \(d_1\) 和 \(d_2\)。
• 正图 \(d_1\) 为回家路，反图 \(d_2\) 为去 \(x\) 的路。
• 枚举每个点的 \(d_1 + d_2\)，取最大值即可。
T5
• \(N\) 个点 \(M\) 条边的有向图，边有黑白两种颜色。现在要给点染色，每个点染成黑或白色。
• 白点只能走它连出去的白边，黑点只能走它连出去的黑边。
• 问是否存在一种染色方案，使得不存在一条 \(1 → n\) 的路径。如果存在这样的染色方案，在第一行输出 \(−1\)，否则输出 \(→ n\) 最长的最短路径长度，每条边长度为 \(1\) 。在第二行，输出对应第一行答案的染色方案。
• \(1 ≤ N, M ≤ 500000\)。
Solution
• 考虑从 \(n\) 出发进行染色，尽可能让每一条路不可经过，这样也是最大化其他点到 \(n\) 的最短路。
• 如果当前为 \(u\) ，点 \(v\) 和 \(u\) 有边，如果只有一种颜色的边，那么这条路是可以禁止经过的，将 \(v\) 设置成与边不同的颜色。如果有不同颜色的边，那么 \(v\) 的颜色无论怎么染色都可以到达 \(u\)。
• 从 \(n\) 开始进行反向 BFS 。
• 当第一次遍历到未染色的点 \(x\)，将点 \(x\) 设为与边不同的颜色。如果遍历到染色的点，并且染色的点与边颜色相同，说明此点无法避开，加入到队列中，更新到 \(n\) 的最短路，直到 \(1\) 入队。
• 时间复杂度为 \(\mathcal{O}(N + M)\)