「JOISC 2013 Day2」建设项目 题解

有 $N$ 个城镇，坐标为 $(X_i, Y_i)$。需要在城镇之间建设道路（只能水平或垂直），并选择一些城镇建设机场。有 $M$ 个矩形障碍区域，道路不能与这些区域相交（包括边界）。每个公司 $k$ 可以建最多 $H_k$ 个机场，每个机场成本 $B_k$。道路成本等于长度。

要求：每个城镇必须能通过道路到达某个有机场的城镇。

求每个公司的最小总成本，若无法满足条件则输出 $-1$。

问题分析

核心观察

1. 连通性要求：所有城镇形成若干个连通分量，每个分量至少需要一个机场
2. 道路约束：只能在同 $x$ 或同 $y$ 坐标的城镇间建道路，且不能穿过障碍
3. 成本权衡：需要在"建机场"和"建道路"之间选择更便宜的方式

关键问题

1. 如何判断两个城镇之间能否建道路？
2. 如何计算最少需要多少个机场？
3. 如何计算最小总成本？

解决方案

第一步：构建可通行图

我们需要确定哪些城镇对之间可以直接连接道路。

垂直连接（相同 $x$ 坐标）：

• 对相同 $x$ 坐标的城镇按 $y$ 坐标排序
• 对于相邻城镇 $(x, y_1)$ 和 $(x, y_2)$，检查线段 $(x, y_1)-(x, y_2)$ 是否与任何障碍相交

水平连接（相同 $y$ 坐标）：

• 对相同 $y$ 坐标的城镇按 $x$ 坐标排序
• 对于相邻城镇 $(x_1, y)$ 和 $(x_2, y)$，检查线段 $(x_1, y)-(x_2, y)$ 是否与任何障碍相交

障碍检查优化：

• 对于垂直线段 $(x, y_1)-(x, y_2)$，只需要检查 $x$ 坐标在 $[P_j, R_j]$ 区间内，且 $[y_1, y_2]$ 与 $[Q_j, S_j]$ 有重叠的障碍
• 可以使用扫描线 + 线段树高效处理

第二步：计算连通分量

用并查集处理所有可通行边，得到 $K$ 个连通分量。

def build_graph(N, towns, obstacles):
    # 按x坐标分组
    towns_by_x = defaultdict(list)
    for i, (x, y) in enumerate(towns):
        towns_by_x[x].append((y, i))
    
    # 按y坐标分组  
    towns_by_y = defaultdict(list)
    for i, (x, y) in enumerate(towns):
        towns_by_y[y].append((x, i))
    
    edges = []
    
    # 处理垂直连接
    for x, pts in towns_by_x.items():
        pts.sort()  # 按y排序
        for i in range(len(pts)-1):
            y1, id1 = pts[i]
            y2, id2 = pts[i+1]
            # 检查线段是否被障碍阻挡
            if not blocked_vertical(x, y1, y2, obstacles):
                edges.append((id1, id2, y2-y1))  # 成本 = 长度
    
    # 处理水平连接
    for y, pts in towns_by_y.items():
        pts.sort()  # 按x排序
        for i in range(len(pts)-1):
            x1, id1 = pts[i]
            x2, id2 = pts[i+1]
            # 检查线段是否被障碍阻挡
            if not blocked_horizontal(y, x1, x2, obstacles):
                edges.append((id1, id2, x2-x1))  # 成本 = 长度
    
    return edges

def find_components(N, edges):
    # 使用并查集找连通分量
    parent = list(range(N))
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    def union(x, y):
        parent[find(x)] = find(y)
    
    for u, v, _ in edges:
        union(u, v)
    
    # 统计连通分量
    comps = defaultdict(list)
    for i in range(N):
        comps[find(i)].append(i)
    
    K = len(comps)
    return K, comps

第三步：计算最小道路成本

对于 $K$ 个连通分量，我们需要用道路连接它们（或者在某些分量建机场）。

关键洞察：

1. 如果我们在所有 $K$ 个分量都建机场，就不需要道路
2. 如果我们只建 $t$ 个机场（$t < K$），就需要用道路将其他分量连接到有机场的分量
3. 连接两个分量的最小成本 = 它们之间的最短可行道路

问题转化为：有 $K$ 个节点（连通分量），我们需要选择 $t$ 个节点建机场，使得每个节点都能连接到某个机场节点，最小化总成本。

这可以看作一个斯坦纳树问题的变种，但对于 $N \leq 200000$ 的数据范围，需要更高效的算法。

第四步：高效算法框架

实际上，由于道路只能是水平或垂直的，我们可以考虑更简单的方法：

1. 最小机场数量：就是连通分量数 $K$
2. 最小道路总长度：连接所有城镇的最小生成树（MST）长度
3. 总成本公式：$\min_{t=K}^{\min(H_k, N)} [B_k \times t + \text{连接所有城镇到t个机场的最小道路成本}]$

但连接所有城镇到 $t$ 个机场的最小道路成本计算困难。不过注意到：

• 如果 $t = K$：不需要道路，成本 = $B_k \times K$
• 如果 $t = 1$：需要连接所有城镇到一个机场，成本 = $B_k + \text{MST总长度}$

对于中间情况，需要在 $K$ 个分量中选择 $t$ 个建机场，其他用道路连接。

第五步：实际可行的解决方案

对于本题的数据范围，一个可行的策略是：

1. 构建完全图，其中节点是连通分量
2. 计算分量之间的最短连接距离
3. 问题转化为：在 $K$ 个节点中选择 $t$ 个作为"中心"（建机场），其他节点连接到最近的"中心"
4. 这是一个经典的设施选址问题

但由于 $K$ 可能很大，需要进一步优化。

第六步：简化版算法（针对子任务）

对于较小的 $M$ 或 $C$，我们可以使用以下算法：

def solve_company(K, B, H, components, distances):
    # K: 连通分量数
    # B: 机场成本
    # H: 最多机场数
    
    if H < K:
        return -1  # 无法满足
    
    # 计算各种机场数量的最小成本
    min_cost = float('inf')
    
    # 如果允许建K个机场，不需要道路
    min_cost = min(min_cost, B * K)
    
    # 如果允许建少于K个机场
    for t in range(1, min(H, K)):
        # 选择t个分量建机场，其他连接
        # 这需要计算选择最优的t个分量的最小成本
        # 可以使用DP或贪心近似
        pass
    
    return min_cost

第七步：完整算法（大纲）

1. 读取输入，存储城镇和障碍
2. 预处理：
   a. 离散化坐标（处理大范围）
   b. 构建障碍数据结构（区间树或线段树）
3. 构建可通行图：
   a. 按x坐标分组，处理垂直连接
   b. 按y坐标分组，处理水平连接
   c. 使用扫描线+线段树快速检查障碍
4. 计算连通分量（并查集）
5. 计算连通分量之间的最小距离：
   a. 对每个连通分量，找到其边界点
   b. 计算分量间的最短可行道路
6. 对于每个公司：
   a. 如果H < K: 输出-1
   b. 否则计算最小成本

关键难点与优化

1. 障碍检查优化

使用扫描线算法：

• 对于垂直检查：将障碍按x坐标区间存储，使用线段树维护y方向的覆盖
• 对于水平检查：类似处理

2. 分量间距离计算

由于道路只能是水平或垂直，两个分量之间的最短路径是曼哈顿距离，但需要避开障碍。这可以通过计算分量边界点的可达性来解决。

3. 设施选址问题

选择 $t$ 个分量建机场的最优方案：

• 对于较小的 $K$，可以枚举或DP
• 对于较大的 $K$，可以使用贪心或近似算法

时间复杂度

• 障碍检查：$O((N+M)\log(N+M))$
• 连通分量：$O(N\alpha(N))$
• 分量间距离：$O(K^2)$ 或优化后 $O(K\log K)$
• 公司处理：$O(C \times \text{某种复杂度})$

算法标签

• 图结构：连通性、最小生成树、设施选址
• 计算几何：线段与矩形相交判断
• 数据结构：并查集、线段树、扫描线
• 离散化：处理大坐标范围
• 贪心/DP：设施选址优化

代码框架

def main():
    N, M, C = map(int, input().split())
    towns = [tuple(map(int, input().split())) for _ in range(N)]
    obstacles = [tuple(map(int, input().split())) for _ in range(M)]
    companies = [tuple(map(int, input().split())) for _ in range(C)]
    
    # 1. 离散化坐标
    all_x = sorted(set([x for x, y in towns] + [p for p,_,r,_ in obstacles] + [r for _,_,r,_ in obstacles]))
    all_y = sorted(set([y for x, y in towns] + [q for _,q,_,s in obstacles] + [s for _,_,_,s in obstacles]))
    
    # 2. 构建可通行图
    edges = build_graph(towns, obstacles, all_x, all_y)
    
    # 3. 计算连通分量
    K, components = find_components(N, edges)
    
    # 4. 计算分量间距离
    comp_dist = compute_component_distances(components, towns, obstacles)
    
    # 5. 处理每个公司
    for B, H in companies:
        if H < K:
            print(-1)
        else:
            cost = compute_min_cost(K, B, H, comp_dist)
            print(cost)

if __name__ == "__main__":
    main()

总结

本题是一道综合性的图论+计算几何难题，核心在于：

1. 高效处理几何约束（道路不能穿过障碍）
2. 计算连通分量
3. 解决设施选址问题（选择哪些分量建机场）

由于数据范围较大，需要精心设计算法和数据结构。在实际竞赛中，可能需要根据子任务特点采用不同的策略。