「51nod1833」环

「51nod1833」环

状压dp即可


题目大意如下。
给出有向图$n \leq 20$。问有多少种方案,可以选取简单环,使其覆盖整个图。

简单环的定义是啥?
或者说,“简单环”能够造成什么限制?
——只算环上的边,每个点的出度和入度都为1
题目转化为以下形式,从$G = (V, E)$中选取$n$条边,使得每个点的出度和入度都是1
dp方式如下$f[i][S]$表示前i个点都有出边,$S$的点有了入边,的情况的个数
妙啊。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

const int N = 20;
int n, m, a[N + 1][N + 1], f[N + 1][(1 << N) + 5];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1, x, y; i <= m; ++i) {
scanf("%d%d", &x, &y);
a[x][y] = 1;
}
f[0][0] = 1;
for (int i = 1; i <= n; ++i)
for (int S = 0; S < (1 << n); ++S)
if (__builtin_popcount(S) + 1 == i)
for (int j = 1; j <= n; ++j)
if (a[i][j] && !(S & (1 << (j - 1))))
f[i][S | (1 << (j - 1))] = (1ll * f[i][S | (1 << (j - 1))] + f[i - 1][S]) % 998244353;
cout << f[n][(1 << n) - 1];
}