优化建图

zjpwdyf · 2024-10-05 15:11:37 · 算法·理论

0. 前言

在图论问题中，有这么一类题型：给定的图极大，甚至都不能直接建出来（TLE/MLE）。

此时就要根据图的性质优化建图，使得新图和原图的答案一致，但规模更小。

注意：本文章中不含各类数据结构优化建图。

1. 建虚拟点

例 1：P7100 [W1] 团

暴力建图是 O(n ^ 2) 的，无法通过。

考虑图的性质：对于点对 (i, j)，连接一条权值为 w_i + w_j 的边。

建造虚拟原点 s。对于每个点 i，连接一条从 i 到 s，边权为 w_i 的边。

不难发现，从 i 到 j 的最短路仍然为 w_i + w_j，但是图的规模从 n ^ 2 降为了 n。

回到原题。对于每个这样的集合，分别建造一个虚拟原点，然后连边。接着在新图上跑最短路即可。