fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. int n, m;  
  12. int adj_mat[19][19]; 
  13. vector<int> adj[19]; 
  14.  
  15. ll dp[1 << 19][19]; 
  16.  
  17. int main() {
  18. 	ios::sync_with_stdio(false); 
  19. 	cin.tie(nullptr); 	
  20. 	cin >> n >> m; 
  21.  
  22. 	for (int i = 0; i < m; i++) {
  23. 		int u, v; 
  24. 		cin >> u >> v; 
  25. 		--u, --v; 
  26. 		adj_mat[u][v] = adj_mat[v][u] = 1;
  27. 		adj[u].push_back(v); 
  28. 		adj[v].push_back(u); 
  29. 	}
  30.  
  31. 	// Đối với mỗi chu trình thì ta lấy đỉnh có số hiệu nhỏ nhất để làm đỉnh đại diện
  32. 	// Khi đó mỗi chu trình sẽ bị đếm qua 2 lần
  33. 	ll ans = 0; 
  34. 	for (int s = 0; s < n; s++) { // Đỉnh đại diện s
  35. 		// dp[mask][v] = Số đường đi xuất phát tại đỉnh s, với s là đỉnh có số hiệu nhỏ nhất, 
  36. 		//               đi qua các đỉnh có trong mask, mỗi đỉnh đúng một lần và kết thúc tại đỉnh v
  37. 		for (int mask = 0; mask < (1 << n); mask++) {			
  38. 			for (int v = 0; v < n; v++) {
  39. 				ll& cur = dp[mask][v];
  40. 				if (mask == (1 << v) && v == s) {
  41. 					cur = 1; 
  42. 					continue;  
  43. 				} 
  44. 				cur = 0;  
  45. 				if (!(mask & (1 << s))) continue;  
  46. 				if (!(mask & (1 << v))) continue; 
  47. 				if (v < s) continue;
  48. 				for (int u : adj[v]) {  
  49. 					int prev_mask = mask ^ (1 << v);   
  50. 					dp[mask][v] += dp[prev_mask][u]; 
  51. 				}
  52. 			}
  53. 		}
  54.  
  55. 		for (int mask = 0; mask < (1 << n); mask++) {
  56. 			int len = __builtin_popcount(mask); 
  57. 			if (len < 3) continue; 
  58. 			for (int v = s; v < n; v++) {
  59. 				ans += dp[mask][v] * adj_mat[v][s]; 
  60. 			}
  61. 		}
  62. 	}
  63.  
  64. 	ans /= 2;  
  65.  
  66. 	cout << ans << '\n'; 
  67. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
4 6
1 2
1 3
1 4
2 3
2 4
3 4
stdout
copy 
7
https://ideone.com/KEhc2a
language:
C++14 (gcc 8.3)
created:
13 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!