C/C++教程

Atcoder CODE FESTIVAL 2016 Grand Final E - Water Distribution

本文主要是介绍Atcoder CODE FESTIVAL 2016 Grand Final E - Water Distribution，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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
这篇关于Atcoder CODE FESTIVAL 2016 Grand Final E - Water Distribution的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航