子集切割型 递推的dp
链接
有别于旅行商那种子集dp f[s][i]这种。。
子集切割型。。他研究的一般是子集和子集的拼凑。。
有点像 区间dp的递推类似。。把当前子集 分割成小子集+小子集。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128_t
#define ar array<int, 2>
#define arr array<int, 3>
int n, m, k, inf = 1LL << 61, mod = 998244353;// 1e9+7;
const int N = 18;
int f[1 << N], a[N];
void solve() {cin >> n >> m;for (int i = 1; i <= m; ++i) {int x, y;cin >> x >> y;x--, y--;a[x] |= 1 << y;//这种记录方式可以快速验证 一些和x有关的信息。a[y] |= 1 << x;}for (int i = 0; i < n; ++i)a[i] |= 1 << i;memset(f, -1, sizeof f);for (int s = 0; s < 1 << n; ++s) {//就是初始化那些自成 完全图的子集 。。int ok = 1;for (int i = 0; i < n; ++i) {if (s >> i & 1 && (a[i]&s) != s)ok = inf;}f[s] = ok;}for (int s = 0; s < 1 << n; ++s)for (int j = s; j >= 0; j = (j - 1)&s) {f[s] = min(f[s], f[j] + f[s ^ j]);//这边就是切割 拼凑if (j == 0)break;}cout << f[(1 << n) - 1];
};signed main() {ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(15);
#ifdef DEBUGfreopen("../1.in", "r", stdin);
#endif//init_f();//init();//expr();// int T; cin >> T; while(T--)solve();return 0;
}