数据范围 \(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