题解 P4496 【[CTSC2009]移民站选址】

disangan233 · 2019-02-27 22:35:13 · 题解

前言

• 这是本蒟蒻的第一篇黑题题解，有误请轻喷。
• 更良好的观看体验：disangan233の博客
• PS：这题本蒟蒻因为某个数组连续开小找了两天两夜。
• 请勿抄袭代码。(反正你代码又交不过)
• 于 2020/10/7修订。

题意简述

• 给你坐标系上 n 个点 a_i(i\in \{1 \cdots n\}) 的坐标，让你求出新建 m 个节点 b_i(i\in \{1 \cdots m\})（可与已存在点重合）后，求 a_i 到 b_i 的最小费用最大流，并输出方案。

具体实现

首先，将题目仔细分析后，得出这样一个结论：

设新节点为 c，为了满足最优解，必定满足：

所以我们把原题就可以拆成横纵坐标来做。

输入1

显然这就是一个带权中位数，不懂的可以去看一维邮局问题。

可以将题意转换为给你 w_i，d(i,j) 为 a_i 到 a_j 的距离，求

先假设 w_i 不存在，那么题目就让你求

显然可以将 x_{a_i} 和 y_{a_i} 分别排序，求出中位数后枚举即可。

那么带权值的中位数即可在普通中位数的前提下，将 a_i 的个数修改为 w_i 即可。

上个图吧：

输入 2-10

首先先考虑跑最小费用最大流，发现 B(i,j) 不好实现，于是考虑转换模型。

以 b_i 建立新节点，并将 b_i 拆成 n+1 个点 b_{i,j}(j\in [1,n+1] )，表示状态 b_i 建在a_j上。
对于每一个 b_{i,j}，向 b_{i,j+1} 建一条流量为 dis(i,j) 的双向边，向 b_{k,j} 建一条流量为 B(i,j)的双向边。

然后将源点向 b_{i,1}，b_{i,n+1} 向汇点，建一条流量为 \infty 的边。