Atcoder CODE FESTIVAL 2016 Grand Final E - Water Distribution
数据范围 \(1\le n\le 15\) 提示我们用状压 \(\text{DP}\). 发现答案满足可二分性, 但二分完答案后并没啥用. 于是考虑发现性质.
引理 1 完全图上的每条边最多被经过一次.
证明 考虑反证法. 若一条边被经过了多次, 则有两次水流要么同向, 要么反向. 两个同向的水流可以被合并到一个水流; 两个反向的水流可以相互抵消.
引理 2 流通传递的水量经过的边的集合必定构成一颗森林.
证明 若经过的边构成了一个环, 则由 引理 1 知, 这个环上的每一条边至多被经过一次, 那么可以将此环上的任意一条边去掉.
由 引理 2 可知, 最优方案的水流一定构成一个森林, 其中森林的每一棵子树都是该子树所在连通块的最小生成树.
于是可以愉快地 \(\text{DP}\) 了: 设 \(f_{S}\) 表示点集合 \(S\) 的最优解. 于是由上述结论就有:
\[f_S=\max\left\{\frac{\sum_{i\in S}a_i-\operatorname{mst}(S)}{\left|S\right|},\,\max_{T\sub S}\left\{\min\{f_T,\,f_{S\backslash T}\}\right\}\right\} \]其中 \(\operatorname{mst}(S)\) 表示为点集合 \(S\) 所构成导出子图的最小生成树的大小. 直接 \(\text{DP}\) 即可.
总时间复杂度: \(\mathrm O(2^n\cdot n^2\log n+3^n)\)
参考代码
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
using real_t = long double;
static constexpr real_t EPS = 1e-10;
static constexpr int Maxn = 16;
__attribute__((__always_inline__)) inline
real_t dist(real_t x1, real_t y1, real_t x2, real_t y2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); }
int n, nn, m;
real_t X[Maxn], Y[Maxn], w[Maxn];
struct edge {
int x, y;
real_t w;
edge() = default;
edge(int x, int y) : x(x), y(y) {
w = dist(X[x], Y[x], X[y], Y[y]);
}
friend bool operator < (const edge &lhs, const edge &rhs) {
return lhs.w < rhs.w;
}
} e[Maxn * Maxn];
int fa[Maxn];
int fnd(int x) { return fa[x] == x ? x : fa[x] = fnd(fa[x]); }
bool vis[Maxn];
real_t cnt[1 << Maxn], sum[1 << Maxn], mst[1 << Maxn];
real_t f[1 << Maxn];
int main(void) {
scanf("%d", &n); nn = (1 << n) - 1;
for (int i = 0; i < n; ++i)
scanf("%Lf %Lf %Lf", &X[i], &Y[i], &w[i]);
for (int s = 1; s <= nn; ++s) {
memset(vis, 0, sizeof(vis));
cnt[s] = sum[s] = 0;
for (int j = 0; j < n; ++j)
if (s >> j & 1)
vis[j] = 1, cnt[s]++, sum[s] += w[j];
for (int i = 0; i < n; ++i) fa[i] = i;
m = 0; mst[s] = 0;
for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j)
if (vis[i] && vis[j]) e[m++] = edge(i, j);
sort(e, e + m);
for (int i = 0; i < m; ++i) {
int x = e[i].x, y = e[i].y;
real_t w = e[i].w;
x = fnd(x), y = fnd(y);
if (x != y) fa[x] = y, mst[s] += w;
}
}
for (int s = 1; s <= nn; ++s) {
f[s] = (sum[s] - mst[s]) / cnt[s];
for (int t = s & s - 1; t; t = (t - 1) & s)
f[s] = max(f[s], min(f[t], f[s ^ t]));
}
printf("%.12Lf\n", f[nn]);
exit(EXIT_SUCCESS);
} // main