题解：AT_cf16_exhibition_final_e Water Distribution

_Cheems · 2024-10-18 10:31:15 · 题解

首先 \max(0,l-dis(x,y)) 不太好看，不妨放宽限制，不与 0 取 \max，这显然不会有影响：现答案肯定不优于原答案，又因为最优情况中肯定不会有 l\le dis(x,y)，所以包含最优解。

然后让传递水的两个城市 x,y 连无向边，权值为负就是 y 向 x 传水。不可能有环，因为可以把环中最大的边去掉，让那份水沿着更小的路径传递。

所以最终构成森林，对于一棵树 T，答案上界就是 \frac{\sum a-\sum e}{|T|}，也就是平均数，而且可以达到该上界，首先随便传水让每个点都到达平均数，然后若一条边被经过多次那么可以直接合并为一次。容易发现，该过程中不会有 a 变成负数（当然是在原来合法的情况下）。

看到 n\le 16 直接状压，先暴力枚举每个连通块，然后 \min(\sum e) 就是最小生成树，最后做一次 dp 合并为森林。

复杂度 O(2^nn^2\log n^2+3^n)，可以通过。

代码

#include<bits/stdc++.h>
using namespace std;

#define db double
const int N = 16;
const db inf = 1e18;
int n, fa[N], m;
db x[N], y[N], v[N], f[1 << N], g[1 << N];
struct edge{int u, v; db w;} e[N * N + 5];

inline int find(int u) {return fa[u] == u ? u : fa[u] = find(fa[u]);}
inline db dist(int a, int b) {return sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));}
signed main(){
    cin >> n;
    for(int i = 0; i < n; ++i) scanf("%lf%lf%lf", &x[i], &y[i], &v[i]); 
    for(int S = 1; S < 1 << n; ++S){
        m = 0;
        for(int i = 0; i < n; ++i)
            if((S >> i) & 1){
                fa[i] = i, f[S] += v[i];
                for(int j = i + 1; j < n; ++j)
                    if((S >> j) & 1)
                        e[++m] = {i, j, dist(i, j)};
            }
        sort(e + 1, e + 1 + m, [](edge A, edge B){return A.w < B.w;});
        for(int i = 1; i <= m; ++i){
            int fu = find(e[i].u), fv = find(e[i].v);
            if(fu != fv) fa[fu] = fv, f[S] -= e[i].w;
        }
        f[S] /= __builtin_popcount(S);
    }
    g[0] = inf;
    for(int S = 1; S < 1 << n; ++S)
        for(int S2 = S; S2; S2 = (S2 - 1) & S)
            g[S] = max(g[S], min(g[S ^ S2], f[S2]));
    printf("%.9lf", g[(1 << n) - 1]);
    return 0;
}