「洛谷P4547」[THUWC 2017] 随机二分图 题解

题目

思路

首先考虑只有第 1 类边的情况，根据期望的线性性，不难得到一个朴素的搜索：搜索每一种完美匹配，并将这个匹配的所有边的概率之积累加到答案，考虑优化，可以将每个点是否被匹配了压缩进一个二进制数，每次只考虑最高的 1 连的边，结合上记忆化搜索，不难发现这是一种 \(O(2^nm)\) 的算法

问题变成了如何将 2 和 3 类边转换为 1 类边或类似 1 类边的情况，发现如果一个 2 类组或 3 类中只选了一条边，概率是 \(50\%\) 和 1 类相同，考虑这种情况下 2 类边两边全选了，那么概率为 \(50\%\times50\%=25\%\) 但实际为 \(50\%\) 于是可以增加一个两边的复合（即选这条边相当于选了两条边），概率为 \(25\%\)，特别地，若这两条边有相同端点，则不加

同理处理 3 类边，由于同时选两条边的概率为 \(0\%\) 故增加一条 \(-25\%\) 的复合边

代码

constexpr int N = 500;
constexpr int Mod = 1000000007, iv2 = (Mod + 1) / 2, iv4 = (Mod + 1) / 4;

class Edge {
 public:
  uint v;
  int p;
  Edge(uint v = 0, int p = 0) : v(v), p(p) {}
} E[N];

int dp(uint sta);

std::unordered_map<uint, int> mp;
int eid;
int n, m;

int main() {
  read(n), read(m);
  for (int i = 1; i <= m; ++i) {
    int op, a, b;
    read(op), read(a), read(b);
    --a, --b;
    int id1 = (1u << a) | (1u << (b + n));
    E[++eid] = Edge(id1, iv2);
    if (op == 0) {
      continue;
    }
    read(a), read(b);
    --a, --b;
    int id2 = (1u << a) | (1u << (b + n));
    E[++eid] = Edge(id2, iv2);
    if (id1 & id2) {
      continue;
    }
    E[++eid] = Edge(id1 | id2, op == 1 ? iv4 : (Mod - iv4));
  }
  write(dp((1u << (n << 1)) - 1) * 1ll * (1 << n) % Mod), EL;
  return 0;
}

int dp(uint sta) {
  if (!sta) {
    return 1;
  }
  auto it = mp.find(sta);
  if (it != mp.end()) {
    return it->second;
  }
  int res = 0;
  for (int i = 1; i <= eid; ++i) {
    uint id = E[i].v;
    if ((id & sta) == id && (id << 1) > sta) {
      res = (res + E[i].p * 1ll * dp(sta ^ id)) % Mod;
    }
  }
  return mp[sta] = res;
}