[ZJOI2015]地震后的幻想乡

第一行两个数n,m，表示地方的数量和边的数量。其中点从1到n标号。
接下来m行，每行两个数a,b，表示点a和点b之间原来有一条边。
这个图不会有重边和自环。

Python3 解法, 执行用时: 284ms, 内存消耗: 5792K, 提交时间: 2023-08-05 09:28:20

def solve(n, m):
    lim = 1 << n
    link = [0] * n
    siz = [0] * lim
    f = [[0.0] * (m + 1) for _ in range(lim)]
    
    for i in range(m):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        link[x] |= (1 << y)
        link[y] |= (1 << x)
    
    for S in range(1, lim):
        siz[S] = siz[S & (S - 1)] + 1
    
    for S1 in range(3, lim):
        if S1 & 1:
            S2 = (S1 - 1) & S1
            while S2 != 0:
                if S2 & 1:
                    T = sum(siz[link[i] & S2] for i in range(n) if ((S1 >> i) & (~S2 >> i) & 1))
                    for i in range(m - T, -1, -1):
                        f[S1][i] += 1.0 / (i + T + 1) - f[S2][i + T]
                S2 = (S2 - 1) & S1
    
    return f[lim - 1][0]

n, m = map(int, input().split())
result = solve(n, m)
print("{:.6f}".format(result))

C++11(clang++ 3.9) 解法, 执行用时: 7ms, 内存消耗: 868K, 提交时间: 2020-03-24 14:36:33

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
const int M = 45 + 1;
bool vis[1 << N][M];
int siz[1 << N], link[N];
double f[1 << N][M];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  int lim = 1 << n;
  for (int i = 0, x, y; i < m; ++i) {
    scanf("%d%d", &x, &y);
    --x; --y;
    link[x] |= (1 << y);
    link[y] |= (1 << x);
  }
  for (int S = 1; S < lim; ++S) siz[S] = siz[S & (S - 1)] + 1;
  for (int S1 = 3; S1 < lim; ++S1) if (S1 & 1) {
    for (int S2 = (S1 - 1) & S1; S2 != 0; S2 = (S2 - 1) & S1) if (S2 & 1) {
      int T = 0;
      for (int i = 0; i < n; ++i) if ((S1 >> i) & (~S2 >> i) & 1)
        T += siz[link[i] & S2];
      for (int i = 0; i + T <= m; ++i)
        f[S1][i] += 1.0 / (i + T + 1) - f[S2][i + T];
    }
  }
  printf("%.6lf\n", f[lim - 1][0]);
  return 0;
}

详情