fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Số modulo theo đề bài (vì kết quả có thể rất lớn)
  5. const int MOD = 1e9 + 7;
  6.  
  7. int n, m;
  8. // Đồ thị lưu danh sách kề (chuyển về 0-index: 0 đến n-1)
  9. vector<int> adj[20];
  10.  
  11. // Bảng DP:
  12. // dp[mask][u]: Số cách đi qua các thành phố trong tập 'mask' và kết thúc tại 'u'
  13. // 1 << 20 tương đương 2^20 (khoảng 1 triệu trạng thái)
  14. long long dp[1 << 20][20];
  15.  
  16. int main(){
  17.     // Tối ưu tốc độ nhập xuất
  18.     cin.tie(0)->sync_with_stdio(0);
  19.  
  20.     // Nếu nộp bài trên máy chấm có file thì mở file, không thì thôi
  21.     if(fopen("Hamiltonian_Flights.inp","r")){
  22.         freopen("Hamiltonian_Flights.inp","r",stdin);
  23.         freopen("Hamiltonian_Flights.out","w",stdout);
  24.     }
  25.  
  26.     cin >> n >> m;
  27.     for(int i = 0; i < m; i++){
  28.         int u, v; cin >> u >> v;
  29.         // Chuyển đỉnh từ 1..n về 0..n-1 để thao tác bit dễ dàng (bit 0 đến bit n-1)
  30.         adj[u-1].push_back(v-1);
  31.     }
  32.  
  33.     // --- CƠ SỞ QUY HOẠCH ĐỘNG ---
  34.     // Ban đầu chỉ có thành phố xuất phát (đỉnh 0) được thăm.
  35.     // Mask = 1 (nhị phân ...0001) nghĩa là chỉ bật bit 0.
  36.     // Kết thúc tại đỉnh 0.
  37.     // Số cách là 1.
  38.     dp[1][0] = 1;
  39.  
  40.     // --- DUYỆT CÁC TRẠNG THÁI ---
  41.     // Duyệt tất cả các trạng thái mask từ 1 đến 2^n - 1
  42.     for(int s = 1; s < (1 << n); s++){
  43.  
  44.         // Điều kiện 1: Hành trình BẮT BUỘC phải chứa đỉnh xuất phát (bit 0)
  45.         // Kiểm tra bit thứ 0 của s. Nếu tắt -> Bỏ qua trường hợp này.
  46.         if(!((s >> 0) & 1)) continue;
  47.  
  48.         // Duyệt đỉnh 'u' mà ta đang đứng hiện tại (u phải nằm trong tập s)
  49.         for(int u = 0; u < n; u++){
  50.  
  51.             // Nếu u không có trong tập s -> Vô lý -> Bỏ qua
  52.             if(!((s >> u) & 1)) continue;
  53.  
  54.             // Nếu chưa có đường nào đi đến trạng thái này -> Bỏ qua để đỡ tốn time
  55.             if(dp[s][u] == 0) continue;
  56.  
  57.             // --- CHUYỂN TRẠNG THÁI (PUSH DP) ---
  58.             // Từ đỉnh u, thử đi tiếp sang các đỉnh kề v
  59.             for(int v : adj[u]){
  60.  
  61.                 // Nếu v đã có trong tập s rồi -> Tức là đã thăm v trước đó
  62.                 // -> Không được thăm lại (vì đây là đường đi đơn) -> Bỏ qua
  63.                 if((s >> v) & 1) continue;
  64.  
  65.                 // Điều kiện 2 (QUAN TRỌNG NHẤT): Về đích sớm
  66.                 // Nếu v là đỉnh đích (n-1), ta chỉ được phép bước vào v 
  67.                 // KHI VÀ CHỈ KHI ta đã đi hết tất cả các thành phố khác.
  68.                 // Kiểm tra: Nếu v là đích VÀ mask mới chưa full (chưa bật hết bit) -> Bỏ
  69.                 if(v == n-1 && (s | (1 << v)) != ((1 << n) - 1)) continue;
  70.  
  71.                 // Tính mask mới khi thêm v vào hành trình
  72.                 // Dùng phép OR để bật bit thứ v
  73.                 int next_s = s | (1 << v);
  74.  
  75.                 // Cộng dồn số cách:
  76.                 // Số cách đến [next_s][v] += Số cách đến [s][u]
  77.                 dp[next_s][v] = (dp[next_s][v] + dp[s][u]) % MOD;
  78.             }
  79.         }
  80.     }
  81.  
  82.     // Kết quả là số cách đi full tất cả thành phố (mask full = 2^n - 1)
  83.     // và kết thúc tại đỉnh đích (n-1)
  84.     cout << dp[(1 << n) - 1][n-1];
  85.  
  86.     return 0;
  87. }
  88.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/vSLwNO
language:
C++14 (gcc 8.3)
created:
5 hours ago
visibility:
public

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!