[ SNOI 2013 ] Quare

柔光的暖阳◎ 2021-12-21 10:33 111阅读 0赞

## Description ##

[题目链接][Link 1]

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

## 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;
    }

转载于:https://www.cnblogs.com/SGCollin/p/10620216.html

[Link 1]: https://lydsy.com/JudgeOnline/problem.php?id=3590