本文共 2790 字，大约阅读时间需要 9 分钟。
一开始写的代码加上各种剪枝后还是超时， 然后看了一下状态压缩后过了，两个代码的具体思想是一样的，状态压缩后可以大大提升性能
#include #include #include #include #include #include #include #include #include #include #include #define maxn 200010#define INF 0x7fffffff#define inf 10000000#define ull unsigned long long#define ll long longusing namespace std;ll st[40], vis[40];int n, m;bool dfs(ll state, int ans, int aim, int k){ if(ans == aim) { if(state == ((ll)1 << n)-1) return true; return false; } for(int i = k; i <= n; ++ i) { if((state|vis[i]) != ((ll)1 << n)-1) return false; if((state|st[i]) == state) continue; if(dfs(state|st[i], ans+1, aim, i+1)) return true; } return false;}void init(){ memset(vis, 0, sizeof(vis)); for(int i = 0; i < n; ++ i) st[i+1] = ((ll)1 << i);}int main(){ while(scanf("%d%d", &n, &m) == 2 && n+m) { init(); for(int i = 0; i < m ; ++ i) { int a, b; scanf("%d%d", &a, &b); st[a] |= ((ll)1 << (b-1)); st[b] |= ((ll)1 << (a-1)); } vis[n] = st[n]; for(int i = n-1; i > 0; -- i) vis[i] = vis[i+1]|st[i]; for(int i = 1; i <= n; ++i) { if(dfs((ll)0, 0, i, 1)) { printf("%d\n", i); break; } }// puts("*****************"); } return 0;}
\*time limit*\
#include #include #include #include #include #include #include #include #include #include #include #define maxn 200010#define INF 0x7fffffff#define inf 10000000#define ull unsigned long long#define ll long longusing namespace std;vector g[40];int vis[40];bool mm[40][40];int n, m;bool checkall(){ for(int i = 1; i <= n; ++ i) if(!vis[i]) return false; return true;}bool checkii(int now){ for(int i = now+1; i <= n; ++ i) if(mm[i][now]) return false; return true;}bool checknow(int now){ if(!vis[now]) return true; for(int i = 0; i < (int)g[now].size(); ++ i) if(!vis[g[now][i]]) return true; return false;}void ok(int now){ vis[now]++; for(int i = 0; i < (int)g[now].size(); ++ i) vis[g[now][i]]++;}void Nok(int now){ vis[now]--; for(int i = 0; i < (int)g[now].size(); ++ i) vis[g[now][i]]--;}bool dfs(int ans, int aim, int k){ if(ans == aim) { if(checkall()) return true; return false; } for(int i = k; i <= n; ++ i) { if(checknow(i)) { ok(i); if(dfs(ans+1, aim, i+1)) return true; Nok(i); } if(!vis[i] && checkii(i)) return false; } return false;}void init(){ memset(vis, 0, sizeof(vis)); memset(mm, 0, sizeof(mm)); for(int i = 1; i <= n; ++ i) g[i].clear();}int main(){ while(scanf("%d%d", &n, &m) == 2 && n+m) { init(); for(int i = 0; i < m ; ++ i) { int a, b; scanf("%d%d", &a, &b); g[a].push_back(b); g[b].push_back(a); mm[a][b] = mm[b][a] = true; } for(int i = 1; i <= n; ++i) { if(dfs(0, i, 1)) { printf("%d\n", i); break; } } } return 0;}
转载于:https://www.cnblogs.com/avema/p/3774266.html