fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define MASK(i) (1LL<<(i)) // Trả về giá trị 2^i
  5. #define BIT(n,i) ((n>>i)&1) // Kiểm tra Bit thứ i của trạng thái n
  6.  
  7. const int INF = 1e9+7; // Giá trị dương vô cùng
  8.  
  9. // Kiểm tra và Cập nhật giá trị nhỏ hơn cho x từ y
  10. template<class _, class __>
  11.     bool minimize(_ &x, const __ y){
  12.         if(x > y){
  13.             x = y;
  14.             return true;
  15.         } else return false;
  16.     }
  17.  
  18. // Kiểm tra và Cập nhật giá trị lớn hơn cho x từ y
  19. template<class _, class __>
  20.     bool maximize(_ &x, const __ y){
  21.         if(x < y){
  22.             x = y;
  23.             return true;
  24.         } else return false;
  25.     }
  26.  
  27. const int N = 63; // Số lượng tỉnh ở Việt Nam
  28. const int Log = 16; // Số lượng tỉnh cần quản lí trong một trạng thái
  29. const long long Min_Population = 1200000; // Dân số thấp nhất của một tỉnh sau khi sáp nhập
  30. const int Min_Area = 6500; // Diện tích nhỏ nhất của một tỉnh sau khi sáp nhập
  31.  
  32. // Tên các tỉnh theo thứ tự chúng tôi sắp xếp
  33. string Province[N] = {
  34.                 "Lang Son", "Quang Ninh", "Hai Duong", "Hai Phong", "Cao Bang",
  35.                 "Bac Kan", "Thai Nguyen", "Bac Giang", "Bac Ninh", "Hung Yen",
  36.                 "Thai Binh", "Ha Giang", "Tuyen Quang", "Vinh Phuc", "Ha Noi",
  37.                 "Ha Nam", "Nam Dinh", "Lao Cai", "Yen Bai", "Phu Tho",
  38.                 "Hoa Binh", "Ninh Binh", "Lai Chau", "Dien Bien", "Son La",
  39.                 "Thanh Hoa","Nghe An", "Ha Tinh", "Quang Binh", "Quang Tri",
  40.                 "Hue", "Da Nang", "Quang Nam", "Kom Tum", "Quang Ngai",
  41.                 "Gia Lai", "Binh Dinh", "Dak Lak", "Phu Yen", "Khanh Hoa",
  42.                 "Ninh Thuan", "Lam Dong", "Dak Nong", "Binh Phuoc", "Binh Thuan",
  43.                 "Dong Nai", "Binh Duong", "Tay Ninh", "Sai Gon", "BRVT",
  44.                 "Long An", "Tien Giang", "Dong Thap", "Ben Tre", "Tra Vinh",
  45.                 "Vinh Long", "Can Tho", "An Giang", "Kien Giang", "Hau Giang",
  46.                 "Soc Trang", "Bac Lieu", "Ca Mau"};
  47.  
  48. // Số thứ tự do đề bài ra
  49. int Real_ID[N] = {
  50.     35, 47, 25, 26, 13, 3, 53, 2, 5, 29, 52, 21, 59, 61, 23, 22, 38, 36, 62, 42,
  51.     28, 40, 33, 17, 50, 54, 39, 24, 44, 48, 55, 14, 45, 32, 46, 20, 10, 15, 43, 30,
  52.     41, 34, 16, 8, 9, 18, 7, 51, 57, 1, 37, 56, 19, 6, 58, 60, 12, 0, 31, 27,
  53.     49, 4, 11
  54. };
  55.  
  56. // Danh sách các tỉnh lân cận của từng tỉnh
  57. vector<int> Edge[N] = {
  58.     {1, 7, 6, 5, 4},             // 0 - Lang Son
  59.     {3, 2, 7, 0},                // 1 - Quang Ninh
  60.     {1, 3, 7, 8, 9, 10},             // 2 - Hai Duong
  61.     {1, 2, 10},             // 3 - Hai Phong
  62.     {0, 5, 12, 11},                   // 4 - Cao Bang
  63.     {0, 6, 12,11,4},      // 5 - Bac Kan
  64.     {0,7,14,13,12,5}, // 6 - Thai Nguyen
  65.     {0,1,2,8,14,6},            // 7 - Bac Giang
  66.     {7,2,9,14},       // 8 - Bac Ninh
  67.     {8,2,10,15,14},    // 9 - Hung Yen
  68.     {3,2,9,15,16},    // 10 - Thai Binh
  69.     {4,12,18,17},          // 11 - Ha Giang
  70.     {4,5,6,13,19,18,11},    // 12 - Tuyen Quang
  71.     {6,14,19,12},  // 13 - Vinh Phuc
  72.     {6,7,8,9,15,20,19,13},          // 14 - Ha Noi
  73.     {9,10,16,21,20,14},  // 15 - Ha Nam
  74.     {10,15,21}, // 16 - Nam Dinh
  75.     {11,18,22},         // 17 - Lao Cai
  76.     {11,12,19,24,22},     // 18 - Yen Bai
  77.     {12,13,14,20,24,18}, // 19 - Phu Tho
  78.     {14,15,21,25,24,19},         // 20 - Hoa Binh
  79.     {15,16,20,25},             // 21 - Ninh Binh
  80.     {17,18,25,23},     // 22 - Lai Chau
  81.     {22,24},             // 23 - Dien Bien
  82.     {23,22,18,19,20,25}, // 24 - Son La
  83.     {21,20,24},          // 25 - Thanh Hoa
  84.     {25,27},                    // 26 - Nghe An
  85.     {26, 28},                // 27 - Ha Tinh
  86.     {27, 29},                // 28 - Quang Binh
  87.     {28, 30},                // 29 - Quang Tri
  88.     {29, 31, 32},            // 30 - Hue
  89.     {30, 32},                // 31 - Da Nang
  90.     {30, 31, 33, 34},            // 32 - Quang Nam
  91.     {32, 34, 35},            // 33 - Kom Tum
  92.     {32, 33, 35, 36},        // 34 - Quang Ngai
  93.     {33, 34, 36, 37, 38},    // 35 - Gia Lai
  94.     {34, 35, 38},            // 36 - Binh Dinh
  95.     {35, 38, 39, 41, 42},    // 37 - Dak Lak
  96.     {35, 36, 37, 39},        // 38 - Phu Yen
  97.     {37, 38, 40, 41},        // 39 - Khanh Hoa
  98.     {39, 41, 44},            // 40 - Ninh Thuan
  99.     {37, 39, 40, 42, 44, 43, 45},    // 41 - Lam Dong
  100.     {37, 41, 43},            // 42 - Dak Nong
  101.     {41, 42, 45, 46, 47},    // 43 - Binh Phuoc
  102.     {40, 41, 45, 49},    // 44 - Binh Thuan
  103.     {44,41,43,49,48,46},        // 45 - Dong Nai
  104.     {43,47,48,45}, // 46 - Binh Duong
  105.     {43, 46, 48, 50},        // 47 - Tay Ninh
  106.     {47,46,45,49,50,51},        // 48 - Sai Gon
  107.     {44, 45, 48},    // 49 - BRVT
  108.     {47, 48, 51, 52},            // 50 - Long An
  109.     {53, 55, 52, 50, 48},        // 51 - Tien Giang
  110.     {50, 51, 55, 56, 57},        // 52 - Dong Thap
  111.     {51, 54, 55},    // 53 - Ben Tre
  112.     {53, 55, 60},            // 54 - Tra Vinh
  113.     {53, 51, 52, 54, 56, 59, 60},            // 55 - Vinh Long
  114.     {52, 55, 57, 58, 59}, // 56 - Can Tho
  115.     {52, 56, 58},    // 57 - An Giang
  116.     {56, 57, 59, 61, 62},            // 58 - Kien Giang
  117.     {55, 56, 60, 61, 58},    // 59 - Hau Giang
  118.     {54, 55, 59, 61},    // 60 - Soc Trang
  119.     {60, 59, 58, 62},        // 61 - Bac Lieu
  120.     {58, 61}                 // 62 - Ca Mau
  121. };
  122.  
  123. // Diện tích các tỉnh
  124. int Area[N] = {
  125.     8310,   // Lang Son
  126.     6208,   // Quang Ninh
  127.     1668,   // Hai Duong
  128.     1527,   // Hai Phong
  129.     6700,   // Cao Bang
  130.     4860,   // Bac Kan
  131.     3522,   // Thai Nguyen
  132.     3896,   // Bac Giang
  133.     823,    // Bac Ninh
  134.     930,    // Hung Yen
  135.     1585,   // Thai Binh
  136.     7928,   // Ha Giang
  137.     5868,   // Tuyen Quang
  138.     1236,   // Vinh Phuc
  139.     3360,   // Ha Noi
  140.     862,    // Ha Nam
  141.     1669,   // Nam Dinh
  142.     6364,   // Lao Cai
  143.     6893,   // Yen Bai
  144.     3535,   // Phu Tho
  145.     4590,   // Hoa Binh
  146.     1412,   // Ninh Binh
  147.     9069,   // Lai Chau
  148.     9540,   // Dien Bien
  149.     14110,  // Son La
  150.     11115,  // Thanh Hoa
  151.     16486,  // Nghe An
  152.     5994,   // Ha Tinh
  153.     7999,   // Quang Binh
  154.     4701,   // Quang Tri
  155.     4947,   // Hue
  156.     1285,   // Da Nang
  157.     10575,  // Quang Nam
  158.     9677,   // Kom Tum
  159.     5155,   // Quang Ngai
  160.     15510,  // Gia Lai
  161.     6066,   // Binh Dinh
  162.     13070,  // Dak Lak
  163.     5026,   // Phu Yen
  164.     5200,   // Khanh Hoa
  165.     3356,   // Ninh Thuan
  166.     9781,   // Lam Dong
  167.     6509,   // Dak Nong
  168.     6874,   // Binh Phuoc
  169.     7943,   // Binh Thuan
  170.     5864,   // Dong Nai
  171.     2695,   // Binh Duong
  172.     4042,   // Tay Ninh
  173.     2095,   // Sai Gon
  174.     1983,   // BRVT
  175.     4495,   // Long An
  176.     2556,   // Tien Giang
  177.     3382,   // Dong Thap
  178.     2380,   // Ben Tre
  179.     2391,   // Tra Vinh
  180.     1526,   // Vinh Long
  181.     1440,   // Can Tho
  182.     3537,   // An Giang
  183.     6353,   // Kien Giang
  184.     1622,   // Hau Giang
  185.     3298,   // Soc Trang
  186.     2668,   // Bac Lieu
  187.     5275    // Ca Mau
  188. };
  189.  
  190. // Dân số các tỉnh
  191. int Population[N] = {
  192.     813978,     // Lang Son
  193.     1393702,    // Quang Ninh
  194.     1971326,    // Hai Duong
  195.     2121841,    // Hai Phong
  196.     555809,     // Cao Bang
  197.     328609,     // Bac Kan
  198.     1361474,    // Thai Nguyen
  199.     1950615,    // Bac Giang
  200.     1543529,    // Bac Ninh
  201.     1313798,    // Hung Yen
  202.     1888184,    // Thai Binh
  203.     908263,     // Ha Giang
  204.     820054,     // Tuyen Quang
  205.     1221803,    // Vinh Phuc
  206.     8685607,    // Ha Noi
  207.     892755,     // Ha Nam
  208.     1892427,    // Nam Dinh
  209.     787066,     // Lao Cai
  210.     863338,     // Yen Bai
  211.     1540608,    // Phu Tho
  212.     892373,     // Hoa Binh
  213.     1027030,    // Ninh Binh
  214.     494626,     // Lai Chau
  215.     653422,     // Dien Bien
  216.     1327430,    // Son La
  217.     3760650,    // Thanh Hoa
  218.     3470988,    // Nghe An
  219.     1329365,    // Ha Tinh
  220.     924169,     // Quang Binh
  221.     658619,     // Quang Tri
  222.     1177624,    // Hue
  223.     1269070,    // Da Nang
  224.     1539468,    // Quang Nam
  225.     598201,     // Kom Tum
  226.     1256952,    // Quang Ngai
  227.     1630311,    // Gia Lai
  228.     1515422,    // Binh Dinh
  229.     1944821,    // Dak Lak
  230.     883298,     // Phu Yen
  231.     1267443,    // Khanh Hoa
  232.     609820,     // Ninh Thuan
  233.     1361129,    // Lam Dong
  234.     692896,     // Dak Nong
  235.     1060448,    // Binh Phuoc
  236.     1266240,    // Binh Thuan
  237.     3341716,    // Dong Nai
  238.     2858815,    // Binh Duong
  239.     1201736,    // Tay Ninh
  240.     9521886,    // Sai Gon (TP. HCM)
  241.     1192863,    // BRVT
  242.     1753041,    // Long An
  243.     1795251,    // Tien Giang
  244.     1600963,    // Dong Thap
  245.     1305281,    // Ben Tre
  246.     1022887,    // Tra Vinh
  247.     1035362,    // Vinh Long
  248.     1268514,    // Can Tho
  249.     1911002,    // An Giang
  250.     1763826,    // Kien Giang
  251.     728924,     // Hau Giang
  252.     1203705,    // Soc Trang
  253.     929439,     // Bac Lieu
  254.     1210843     // Ca Mau
  255. };
  256.  
  257. int trace[N][MASK(Log)]; // Mảng truy vết
  258.  
  259. int f[N][MASK(Log)]; // Hàm mục tiêu
  260.  
  261. void prepare() {
  262.     // Bài toán cơ sở
  263.     for (int i=0;i<N;i++) {
  264.         for (int j=0;j<MASK(Log);j++) {
  265.             f[i][j] = INF;
  266.             // Dương vô cùng nếu hàm mục tiêu cần tìm MIN
  267.             // Âm vô cùng nếu hàm mục tiêu cần tìm MAX
  268.             trace[i][j] = 0;
  269.         }
  270.     }
  271.     f[0][0] = 0; // Giá trị của trạng trái 0000...0
  272. }
  273.  
  274. bool Check_Population_Area(vector<int> ds) {
  275.     // Kiểm tra điều kiện về dân số và diện tích của cụm tỉnh mới [ds]
  276.     int Sum_Area = 0;
  277.     long long Sum_Population = 0;
  278.     for (int x : ds) {
  279.         Sum_Area += Area[x];
  280.         Sum_Population += Population[x];
  281.     }
  282.     return Sum_Area >= Min_Area && Sum_Population >= Min_Population;
  283. }
  284.  
  285. void Push(int pos,int OldMask,vector<int> ds) {
  286. //Cập nhật giá trị tối ưu và lưu vết cho trạng thái mới khi sáp nhập cụm tỉnh [ds]
  287.  
  288.     // Xét dân số và diện tích của cụm tỉnh [ds]
  289.     if (!Check_Population_Area(ds)) return;
  290.  
  291.     // Xét các tỉnh trong [ds] đã được sáp nhập hay chưa
  292.     for (int x : ds) if (BIT(OldMask,x - pos)) return;
  293.  
  294.     // Tạo ra trạng thái mới từ trạng thái cũ sau khi sáp nhập cụm tỉnh [ds]
  295.     int NewMask = OldMask;
  296.     for (int x : ds) NewMask |= MASK(x - pos);
  297.  
  298.     // Cập nhập giá trị tối ưu cho trạng thái mới
  299.     if (minimize(f[pos][NewMask],f[pos][OldMask] + (ds.size() == 3))) {
  300.         // Lưu vết cho trạng thái mới
  301.         trace[pos][NewMask] = 0;
  302.         for (int x : ds) trace[pos][NewMask] |= MASK(x - pos);
  303.     }
  304. }
  305.  
  306. void Update_To_Next_Province(int pos) {
  307.     // Cập nhật cửa sổ để xét đỉnh tiếp theo
  308.     for (int mask=0;mask < MASK(Log);mask++) {
  309.         if (BIT(mask,0)) minimize(f[pos+1][mask>>1],f[pos][mask]);
  310.         // minimize nếu hàm mục tiêu là MIN
  311.         // maximize nếu hàm mục tiêu là MAX
  312.     }
  313. }
  314.  
  315. void sol() {
  316.     // Quy hoạch động bitmask
  317.     for (int x=0;x<N;x++) {
  318.         for (int mask=0;mask<MASK(Log);mask++) {
  319.             if (BIT(mask,0) == 0 && f[x][mask] < INF) {
  320.                 Push(x,mask,{x}); // Xét tỉnh mới chỉ gồm một tỉnh x
  321.                 for (int y : Edge[x]) {
  322.                     if (y <= x) continue;
  323.                     Push(x,mask,{x,y}); // Xét tỉnh mới gồm 2 tỉnh x và một đỉnh kề x
  324.                     for (int z:Edge[y]) {
  325.                         if (z <= x) continue;
  326.                         Push(x,mask,{x,y,z});   /*Xét cụm tỉnh mới gồm 3 tỉnh :
  327.                                                     tỉnh x
  328.                                                     tỉnh y giáp với tỉnh x
  329.                                                     tỉnh z giáp với tỉnh y
  330.                                                 */
  331.                     }
  332.                     for (int z:Edge[x]) {
  333.                         if (z <= x || z == y) continue;
  334.                         Push(x,mask,{x,y,z}); /*Xét cụm tỉnh mới gồm 3 tỉnh:
  335.                                                     tỉnh x
  336.                                                     tỉnh y giáp với tỉnh x
  337.                                                     tỉnh z giáp với tỉnh x
  338.                                                 */
  339.                     }
  340.                 }
  341.             }
  342.         }
  343.         if (x == N - 1) continue;
  344.         // cập nhật cửa sổ để xét đỉnh tiếp theo
  345.         Update_To_Next_Province(x);
  346.     }
  347.     // Truy vết
  348.     int pos = N-1;
  349.     int mask = 1;
  350.     while (pos != 0 || mask != 0) {
  351.         if (trace[pos][mask] == 0) {
  352.             pos--;
  353.             mask = mask << 1 | 1;
  354.         }
  355.         else {
  356.             int tmp = trace[pos][mask];
  357.             for (int i=0;i<Log;i++) {
  358.                 if (BIT(tmp,i)) {
  359.                     cout << Real_ID[pos+i] << ' ';
  360.                     mask ^= MASK(i);
  361.                 }
  362.             }
  363.             cout << '\n';
  364.         }
  365.     }
  366. }
  367.  
  368. int main() {
  369. //    freopen("ketqua.out","w",stdout);
  370.     prepare();
  371.     sol();
  372. }
  373.  
Success #stdin #stdout 0.03s 35960KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
31 11 
12 0 27 
58 49 4 
19 6 60 
37 56 
7 51 
18 57 
9 1 
34 8 
30 41 
15 16 
10 43 
20 
32 46 
14 45 
48 55 
24 44 
39 
62 17 50 
36 33 
38 40 54 
59 61 
52 22 28 
29 23 42 
3 53 
13 21 
47 25 26 
35 2 5
https://ideone.com/Shz68b
language:
C++ (gcc 8.3)
created:
10 days 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!