70286 - CSP-S第一轮同测模拟卷1阅读程序3
统计题目(材料题)
01 #include <iostream>
02 #include <vector>
03 #include <algorithm>
04 using namespace std;
05
06 const int INF = 1e9;
07 int n, m;
08 vector<int> adj[20];
09 int dp[1 << 20];
10
11 int solve(int mask) {
12 if (mask == (1 << n) - 1)
13 return 0;
14 if (dp[mask] != -1)
15 return dp[mask];
16 int u = -1;
17 for (int i = 0; i < n; i++) {
18 if (!(mask & (1 << i))) {
19 u = i;
20 break;
21 }
22 }
23 int res = INF;
24 int take = mask | (1 << u);
25 for (int v : adj[u])
26 take |= (1 << v);
27 res = min(res, solve(take) + 1);
28 bool ok = true;
29 for (int v : adj[u]) {
30 if (!(mask & (1 << v))) {
31 ok = false;
32 break;
33 }
34 }
35 if (ok) {
36 res = min(res, solve(mask | (1 << u)));
37 }
38 return dp[mask] = res;
39 }
40
41 int main() {
42 cin >> n >> m;
43 for (int i = 0; i < m; i++) {
44 int u, v;
45 cin >> u >> v;
46 u--;
47 v--;
48 adj[u].push_back(v);
49 adj[v].push_back(u);
50 }
51 for (int i = 0; i < (1 << n); i++)
52 dp[i] = -1;
53 cout << solve(0) << endl;
54 return 0;
55 }
关注我们
