题目链接
点我跳转
题目大意
解题思路
AC_Code
#include<bits/stdc++.h>
using namespace std;
const int N = 1LL << 19 , M = 20;
int n , m , dp[N] , ok[N] , g[M][M];
signed main()
{
cin >> n >> m;
for(int i = 1 ; i <= m ; i ++)
{
int x , y;
cin >> x >> y;
g[x][y] = g[y][x] = 1;
}
int sum = 1 << n;
for(int i = 0 ; i < sum ; i ++)
{
ok[i] = 1;
for(int j = 1 ; j <= n ; j ++) if(i >> (j - 1) & 1)
{
for(int k = j + 1 ; k <= n ; k ++) if(i >> (k - 1) & 1)
{
if(!g[j][k]) { ok[i] = 0 ; break ; }
}
if(!ok[i]) break ;
}
dp[i] = 1e9;
}
dp[0] = 0;
for(int i = 0 ; i < sum ; i ++)
{
for(int j = i ; j ; j = (j - 1) & i) if(ok[j])
{
dp[i] = min(dp[i] , dp[i ^ j] + 1);
}
}
cout << dp[sum - 1] << '\n';
return 0;
}