[ SNOI 2013 ] Quare

Description

题目链接

求一张无向带权图的边双连通生成子图的最小代价。

Solution

核心的思路是，一个点双连通分量肯定是一堆环的并。

考虑增量地构造这个边双连通图，每次把一个环并进去，相当于加入了一条链。

那么这个转移需要：原集合的代价，链的代价，链的端点连入集合的代价。

设 \(A\) 为新图点集，\(S\) 为原图点集，设 \(f[S]\) 表示点集 \(S\) 构成边双连通分量的最小代价。

设 \(T\) 为新加入链的点集，\(u,v\) 分别为加入的链的端点，设 \(g[u][v][T]\) 表示该链的最小代价。

设 \(mm[u][S]\) 表示点 \(u\) 向集合 \(S\) 中的点所连边中，边权最小值。

\[f[A]=f[S]+g[u][v][T]+mn[u][S]+mn[v][S]
\]

但是注意，如果新加入的链退化成了一个点，加入的代价就算少了。

因此设 \(sec[u][S]\) 表示点 \(u\) 向集合 \(S\) 中的点所连边中，边权次小值。

那么对于 \(u=v\) 的情况：

\[f[A]=f[S]+g[u][u][T]+mn[u][S]+sec[u][S]
\]

预处理 \(mn\) 和 \(sec\) 复杂度 \(\mathcal O(n^2\times 2^n)\)

预处理 \(g\) 暴力枚举一个端点的变化，复杂度 \(\mathcal O(n^3\times 2^n)\)

计算 \(f\) 需要枚举子集，然后枚举 \(u, v\) ，复杂度 \(\mathcal O(n^2\times 3^n )\)

#include <cmath>

#include <cstdio>

#include <cctype>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 15

#define M 105

#define S 4105

using namespace std;

inline int rd() {

  int x = 0;

  char c = getchar();

  while (!isdigit(c)) c = getchar();

  while (isdigit(c)) {

    x = x * 10 + (c ^ 48); c = getchar();

  }

  return x;

}

int n, m, tot, lim, hd[N];

struct edge{int w, to, nxt;} e[M << 1];

inline void add(int u, int v, int w) {

  e[++tot].to = v; e[tot].w = w;

  e[tot].nxt = hd[u]; hd[u] = tot;

}

//mn[i][S]: i 到 S 最短路

//sec[i][S]: i 到 S 次短路

//g[i][j][S]: 一条链，节点集合为 S, 端点分别为 i, j

//f[S]: 集合为 S 的合法方案

int f[S], g[N][N][S], mn[N][S], sec[N][S];

inline void mmin(int &x, int y) {x = min(x, y);}

inline int countbit(int s) {

  int res = 0;

  for (int i = 0; i < n; ++i)

    res += ((s & (1 << i)) > 0);

  return res;

}

inline void work() {

  n = rd(); m = rd();

  tot = 0; lim = (1 << n);

  for (int i = 0; i <= n; ++i) hd[i] = 0;

  for (int i = 1, u, v, w; i <= m; ++i) {

    u = rd() - 1; v = rd() - 1; w = rd();

    add(u, v, w); add(v, u, w);

  }

  memset(f, 0x1f, sizeof(f));

  memset(g, 0x1f, sizeof(g));

  memset(mn, 0x1f, sizeof(mn));

  memset(sec, 0x1f, sizeof(sec));

  int inf = f[0];

  //处理 mn 和 sec

  for (int s = 1; s < lim; ++s)

    for (int u = 0; u < n; ++u)

      if ((s & (1 << u)) == 0)

        for (int i = hd[u], v; i; i = e[i].nxt) {

          v = e[i].to;

          if ((s & (1 << v)) == 0) continue;

          if (e[i].w < mn[u][s]) {

            sec[u][s] = mn[u][s];

            mn[u][s] = e[i].w; continue;

          } else sec[u][s] = min(sec[u][s], e[i].w);

        }

  //处理 g

  for (int u = 0; u < n; ++u) g[u][u][1 << u] = 0;

  for (int s = 1; s < lim; ++s)

    for (int u = 0; u < n; ++u)

      for (int x = 0; x < n; ++x)

        if (g[u][x][s] < inf)

          for (int i = hd[u], v; i; i = e[i].nxt) {

            v = e[i].to;

            if (s & (1 << v)) continue;

            mmin(g[v][x][s | (1 << v)], g[u][x][s] + e[i].w);

          }

  //处理 f

  for (int u = 0; u < n; ++u) f[1 << u] = 0;

  for (int nw = 1; nw < lim; ++nw)

    if (countbit(nw) >= 2) {

      for (int s = nw & (nw - 1); s; s = (s - 1) & nw) {

        int t = nw - s;

        for (int u = 0; u < n; ++u)

          if (s & (1 << u)) for (int v = 0; v < n; ++v)

            if (s & (1 << v) && g[u][v][s] < inf) {

              if (u == v) f[nw] = min(f[nw], f[t] + g[u][v][s] + mn[u][t] + sec[u][t]);

              else f[nw] = min(f[nw], f[t] + g[u][v][s] + mn[u][t] + mn[v][t]);

            }

      }

    }

    if (f[lim - 1] == inf) puts("impossible");

    else printf("%d\n", f[lim - 1]);

}

int main() {

  int testcase = rd();

  while (testcase--) work();

  return 0;

}

巴特西

[ SNOI 2013 ] Quare

Description

Solution

最新文章

热门文章