题目链接：
思路：首先可以预处理出在每个顶点的状态的合法状态vis[u][state], 然后标记那些合法状态mark[state]。最后就是记忆化搜索了，对于当前状态state,我们有res = min(res, 1 + Solve(state ^ substate)), 其中substate为state的子状态，并且substate = (substate - 1) & state.那么最终就是要求Solve((1 << n) - 1)了。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 int n, m; 9 bool vis[16][1 << 16];10 bool mark[1 << 16];11 int dp[1 << 16];12 vector g[16];13 14 void dfs(int u, int state)15 {16 vis[u][state] = true;17 mark[state] = true;18 for (int i = 0; i < (int)g[u].size(); i++) {19 int v = g[u][i];20 if (!vis[v][state | (1 << v)]) {21 dfs(v, state | (1 << v));22 }23 }24 }25 26 int Solve(int state)27 {28 if (state == 0) return 0;29 if (dp[state] != -1) return dp[state];30 int res = 16;31 for (int i = state; i > 0; i = (i - 1) & state) {32 if (mark[i]) {33 res = min(res, 1 + Solve(state ^ i));34 }35 }36 return dp[state] = res;37 }38 39 40 int main()41 {42 int _case, t = 1;43 scanf("%d", &_case);44 while (_case--) {45 scanf("%d %d", &n, &m);46 for (int i = 0; i < n; i++) g[i].clear();47 while (m--) {48 int u, v;49 scanf("%d %d", &u, &v);50 u--, v--;51 g[u].push_back(v);52 }53 memset(vis, false, sizeof(vis));54 memset(mark, false, sizeof(mark));55 for (int i = 0; i < n; i++) dfs(i, 1 << i);56 memset(dp, -1, sizeof(dp));57 printf("Case %d: %d\n", t++, Solve((1 << n) -1));58 }59 return 0;60 }