fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define MASK(i) (1LL<<(i))
  5. #define BIT(n,i) ((n>>i)&1)
  6. #define SQR(n) (1LL*n*n)
  7.  
  8. const int INF = 1e9+7;
  9.  
  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. template<class _, class __>
  18.     bool maximize(_ &x, const __ y){
  19.         if(x < y){
  20.             x = y;
  21.             return true;
  22.         } else return false;
  23.     }
  24.  
  25. const int N = 63; // Số tỉnh nước Việt Nam
  26. const int MaxM = 35; // Số lượng tỉnh tối đa sau khi sáp nhập
  27. const int Log = 16; // Số lượng tỉnh cần quản lí trong một trạng thái
  28. const long long Min_Population = 1200000;
  29. const int Min_Area = 6500;
  30.  
  31. string Province[N] = {"Lang Son", "Quang Ninh", "Hai Duong", "Hai Phong", "Cao Bang",
  32.                 "Bac Kan", "Thai Nguyen", "Bac Giang", "Bac Ninh", "Hung Yen",
  33.                 "Thai Binh", "Ha Giang", "Tuyen Quang", "Vinh Phuc", "Ha Noi",
  34.                 "Ha Nam", "Nam Dinh", "Lao Cai", "Yen Bai", "Phu Tho",
  35.                 "Hoa Binh", "Ninh Binh", "Lai Chau", "Dien Bien", "Son La",
  36.                 "Thanh Hoa","Nghe An", "Ha Tinh", "Quang Binh", "Quang Tri",
  37.                 "Hue", "Da Nang", "Quang Nam", "Kom Tum", "Quang Ngai",
  38.                 "Gia Lai", "Binh Dinh", "Dak Lak", "Phu Yen", "Khanh Hoa",
  39.                 "Ninh Thuan", "Lam Dong", "Dak Nong", "Binh Phuoc", "Binh Thuan",
  40.                 "Dong Nai", "Binh Duong", "Tay Ninh", "Sai Gon", "BRVT",
  41.                 "Long An", "Tien Giang", "Dong Thap", "Ben Tre", "Tra Vinh",
  42.                 "Vinh Long", "Can Tho", "An Giang", "Kien Giang", "Hau Giang",
  43.                 "Soc Trang", "Bac Lieu", "Ca Mau"};
  44.  
  45. int Real_ID[N] = {
  46.     35, 47, 25, 26, 13, 3, 53, 2, 5, 29, 52, 21, 59, 61, 23, 22, 38, 36, 62, 42,
  47.     28, 40, 33, 17, 50, 54, 39, 24, 44, 48, 55, 14, 45, 32, 46, 20, 10, 15, 43, 30,
  48.     41, 34, 16, 8, 9, 18, 7, 51, 57, 1, 37, 56, 19, 6, 58, 60, 12, 0, 31, 27,
  49.     49, 4, 11
  50. };
  51.  
  52. vector<int> Edge[N] = {
  53.     {1, 7, 6, 5, 4},             // 0 - Lang Son
  54.     {3, 2, 7, 0},                // 1 - Quang Ninh
  55.     {1, 3, 7, 8, 9, 10},             // 2 - Hai Duong
  56.     {1, 2, 10},             // 3 - Hai Phong
  57.     {0, 5, 12, 11},                   // 4 - Cao Bang
  58.     {0, 6, 12,11,4},      // 5 - Bac Kan
  59.     {0,7,14,13,12,5}, // 6 - Thai Nguyen
  60.     {0,1,2,8,14,6},            // 7 - Bac Giang
  61.     {7,2,9,14},       // 8 - Bac Ninh
  62.     {8,2,10,15,14},    // 9 - Hung Yen
  63.     {3,2,9,15,16},    // 10 - Thai Binh
  64.     {4,12,18,17},          // 11 - Ha Giang
  65.     {4,5,6,13,19,18,11},    // 12 - Tuyen Quang
  66.     {6,14,19,12},  // 13 - Vinh Phuc
  67.     {6,7,8,9,15,20,19,13},          // 14 - Ha Noi
  68.     {9,10,16,21,20,14},  // 15 - Ha Nam
  69.     {10,15,21}, // 16 - Nam Dinh
  70.     {11,18,22},         // 17 - Lao Cai
  71.     {11,12,19,24,22},     // 18 - Yen Bai
  72.     {12,13,14,20,24,18}, // 19 - Phu Tho
  73.     {14,15,21,25,24,19},         // 20 - Hoa Binh
  74.     {15,16,20,25},             // 21 - Ninh Binh
  75.     {17,18,25,23},     // 22 - Lai Chau
  76.     {22,24},             // 23 - Dien Bien
  77.     {23,22,18,19,20,25}, // 24 - Son La
  78.     {21,20,24},          // 25 - Thanh Hoa
  79.     {25,27},                    // 26 - Nghe An
  80.     {26, 28},                // 27 - Ha Tinh
  81.     {27, 29},                // 28 - Quang Binh
  82.     {28, 30},                // 29 - Quang Tri
  83.     {29, 31, 32},            // 30 - Hue
  84.     {30, 32},                // 31 - Da Nang
  85.     {30, 31, 33, 34},            // 32 - Quang Nam
  86.     {32, 34, 35},            // 33 - Kom Tum
  87.     {32, 33, 36},        // 34 - Quang Ngai
  88.     {33, 36, 37, 38},    // 35 - Gia Lai
  89.     {34, 35, 38},            // 36 - Binh Dinh
  90.     {35, 38, 39, 41, 42},    // 37 - Dak Lak
  91.     {35, 36, 37, 39},        // 38 - Phu Yen
  92.     {37, 38, 40, 41},        // 39 - Khanh Hoa
  93.     {39, 41, 44},            // 40 - Ninh Thuan
  94.     {37, 39, 40, 42, 44, 43, 45},    // 41 - Lam Dong
  95.     {37, 41, 43},            // 42 - Dak Nong
  96.     {41, 42, 45, 46, 47},    // 43 - Binh Phuoc
  97.     {40, 41, 45, 49},    // 44 - Binh Thuan
  98.     {44,41,43,49,48,46},        // 45 - Dong Nai
  99.     {43,47,48,45}, // 46 - Binh Duong
  100.     {43, 46, 48, 50},        // 47 - Tay Ninh
  101.     {47,46,45,50},        // 48 - Sai Gon
  102.     {44, 45},    // 49 - BRVT
  103.     {47, 48, 51, 52},            // 50 - Long An
  104.     {53, 55, 52, 50},        // 51 - Tien Giang
  105.     {50, 51, 55, 56, 57},        // 52 - Dong Thap
  106.     {51, 54, 55},    // 53 - Ben Tre
  107.     {53, 55, 60},            // 54 - Tra Vinh
  108.     {53, 51, 52, 54, 56, 59, 60},            // 55 - Vinh Long
  109.     {52, 55, 57, 58, 59}, // 56 - Can Tho
  110.     {52, 56, 58},    // 57 - An Giang
  111.     {56, 57, 59, 61, 62},            // 58 - Kien Giang
  112.     {55, 56, 60, 61, 58},    // 59 - Hau Giang
  113.     {54, 55, 59, 61},    // 60 - Soc Trang
  114.     {60, 59, 58, 62},        // 61 - Bac Lieu
  115.     {58, 61}                 // 62 - Ca Mau
  116. };
  117. /*
  118.         Khác với danh sách kề đã liệt kê ở câu 3: Một số cặp đỉnh sẽ không được coi
  119.     không kề nhauvì đường giáp ranh giữa hai tỉnh khá nhỏ.
  120.             Quãng Ngãi - Gia Lai
  121.             TP HCM - BRVT
  122.             TP HCM - Tiền Giang
  123. */
  124.  
  125. int Area[N] = {
  126.     8310,   // Lang Son
  127.     6208,   // Quang Ninh
  128.     1668,   // Hai Duong
  129.     1527,   // Hai Phong
  130.     6700,   // Cao Bang
  131.     4860,   // Bac Kan
  132.     3522,   // Thai Nguyen
  133.     3896,   // Bac Giang
  134.     823,    // Bac Ninh
  135.     930,    // Hung Yen
  136.     1585,   // Thai Binh
  137.     7928,   // Ha Giang
  138.     5868,   // Tuyen Quang
  139.     1236,   // Vinh Phuc
  140.     3360,   // Ha Noi
  141.     862,    // Ha Nam
  142.     1669,   // Nam Dinh
  143.     6364,   // Lao Cai
  144.     6893,   // Yen Bai
  145.     3535,   // Phu Tho
  146.     4590,   // Hoa Binh
  147.     1412,   // Ninh Binh
  148.     9069,   // Lai Chau
  149.     9540,   // Dien Bien
  150.     14110,  // Son La
  151.     11115,  // Thanh Hoa
  152.     16486,  // Nghe An
  153.     5994,   // Ha Tinh
  154.     7999,   // Quang Binh
  155.     4701,   // Quang Tri
  156.     4947,   // Hue
  157.     1285,   // Da Nang
  158.     10575,  // Quang Nam
  159.     9677,   // Kom Tum
  160.     5155,   // Quang Ngai
  161.     15510,  // Gia Lai
  162.     6066,   // Binh Dinh
  163.     13070,  // Dak Lak
  164.     5026,   // Phu Yen
  165.     5200,   // Khanh Hoa
  166.     3356,   // Ninh Thuan
  167.     9781,   // Lam Dong
  168.     6509,   // Dak Nong
  169.     6874,   // Binh Phuoc
  170.     7943,   // Binh Thuan
  171.     5864,   // Dong Nai
  172.     2695,   // Binh Duong
  173.     4042,   // Tay Ninh
  174.     2095,   // Sai Gon
  175.     1983,   // BRVT
  176.     4495,   // Long An
  177.     2556,   // Tien Giang
  178.     3382,   // Dong Thap
  179.     2380,   // Ben Tre
  180.     2391,   // Tra Vinh
  181.     1526,   // Vinh Long
  182.     1440,   // Can Tho
  183.     3537,   // An Giang
  184.     6353,   // Kien Giang
  185.     1622,   // Hau Giang
  186.     3298,   // Soc Trang
  187.     2668,   // Bac Lieu
  188.     5275    // Ca Mau
  189. };
  190.  
  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 GRDP[N] = {
  258.     50,  // Lang Son
  259.     348, // Quang Ninh
  260.     212, // Hai Duong
  261.     446, // Hai Phong
  262.     25,  // Cao Bang
  263.     19,  // Bac Kan
  264.     167, // Thai Nguyen
  265.     207, // Bac Giang
  266.     232, // Bac Ninh
  267.     160, // Hung Yen
  268.     71,  // Thai Binh
  269.     36,  // Ha Giang
  270.     50,  // Tuyen Quang
  271.     173, // Vinh Phuc
  272.     1430, // Ha Noi
  273.     56,  // Ha Nam
  274.     113, // Nam Dinh
  275.     77,  // Lao Cai
  276.     49,  // Yen Bai
  277.     107, // Phu Tho
  278.     72,  // Hoa Binh
  279.     99,  // Ninh Binh
  280.     31,  // Lai Chau
  281.     32,  // Dien Bien
  282.     77,  // Son La
  283.     319, // Thanh Hoa
  284.     217, // Nghe An
  285.     113, // Ha Tinh
  286.     60,  // Quang Binh
  287.     54,  // Quang Tri
  288.     80,  // Hue
  289.     151, // Da Nang
  290.     129, // Quang Nam
  291.     41,  // Kom Tum
  292.     133, // Quang Ngai
  293.     111, // Gia Lai
  294.     131, // Binh Dinh
  295.     141, // Dak Lak
  296.     63,  // Phu Yen
  297.     129, // Khanh Hoa
  298.     60,  // Ninh Thuan
  299.     13,  // Lam Dong
  300.     56,  // Dak Nong
  301.     115, // Binh Phuoc
  302.     121, // Binh Thuan
  303.     494, // Dong Nai
  304.     520, // Binh Duong
  305.     124, // Tay Ninh
  306.     1778, // Sai Gon (TP. Ho Chi Minh)
  307.     417, // BRVT
  308.     189, // Long An
  309.     137, // Tien Giang
  310.     124, // Dong Thap
  311.     74,  // Ben Tre
  312.     97,  // Tra Vinh
  313.     84,  // Vinh Long
  314.     133, // Can Tho
  315.     127, // An Giang
  316.     144, // Kien Giang
  317.     68,  // Hau Giang
  318.     80,  // Soc Trang
  319.     66,  // Bac Lieu
  320.     88   // Ca Mau
  321. };
  322.  
  323. int trace[N][MaxM][MASK(Log)];
  324.  
  325. int f[N][MaxM][MASK(Log)];
  326.  
  327. int sumGRDP = 0;
  328.  
  329. void prepare() {
  330.     for (int i=0;i<N;i++) {
  331.         for (int j=0;j<MASK(Log);j++) {
  332.             for (int m=0;m<MaxM;m++) {
  333.                 f[i][m][j] = INF; // Đặt tất cả giá trị về dương vô cùng vì hàm mục tiêu là MIN
  334.                 trace[i][m][j] = 0;
  335.             }
  336.         }
  337.     }
  338.     f[0][0][0] = 0;
  339. }
  340.  
  341. bool IsAppear(int u,vector<int> & ds)  {
  342.     // Kiểm tra đỉnh thứ u có nằm trong cụm tỉnh [ds] không
  343.     for (int x : ds) {
  344.         if (x == u) return true;
  345.     }
  346.     return false;
  347. }
  348.  
  349. bool Check(vector<int> ds) {
  350. //Kiểm tra khả năng sáp nhập của cụm tỉnh [ds]
  351.  
  352.     // Tp HCM không sáp nhập với tỉnh nào khác
  353.     if (IsAppear(48,ds)) return ds.size() == 1;
  354.  
  355.     // Hà Nội sáp nhập với nhiều nhất 1 tỉnh
  356.     if (IsAppear(14,ds)) return ds.size() <= 2;
  357.  
  358.     // Các cặp tỉnh không thể sáp nhập vì vấn đề về giao thông
  359.     if (IsAppear(33,ds) && IsAppear(34,ds)) return false;
  360.     if (IsAppear(22,ds) && IsAppear(23,ds)) return false;
  361.     if (IsAppear(18,ds) && IsAppear(11,ds)) return false;
  362.     if (IsAppear(35,ds) && IsAppear(38,ds)) return false;
  363.     if (IsAppear(37,ds) && IsAppear(39,ds)) return false;
  364.  
  365.     // Xét các điều kiện về diện tích và dân số
  366.     int Sum_Area = 0;
  367.     long long Sum_Population = 0;
  368.     for (int x : ds) {
  369.         Sum_Area += Area[x];
  370.         Sum_Population += Population[x];
  371.     }
  372.     return Sum_Area >= Min_Area && Sum_Population >= Min_Population;
  373. }
  374.  
  375. int SumGRDP(vector<int> & ds) {
  376.     int sum = 0;
  377.     for (int x : ds) {
  378.         sum += GRDP[x];
  379.     }
  380.     return sum;
  381. }
  382.  
  383. void Push(int pos,int m,int OldMask,vector<int> ds) {
  384. // 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]
  385.     if (!Check(ds)) return;
  386.     for (int x : ds) if (BIT(OldMask,x - pos)) return;
  387.     int NewMask = OldMask;
  388.     for (int x : ds) NewMask |= MASK(x - pos);
  389.     if (minimize(f[pos][m+1][NewMask],f[pos][m][OldMask] + SQR(SumGRDP(ds)))) {
  390.         trace[pos][m+1][NewMask] = 0;
  391.         for (int x : ds) trace[pos][m+1][NewMask] |= MASK(x-pos);
  392.     }
  393. }
  394.  
  395. void Update_To_Next_Province(int pos) {
  396. //Cập nhật cửa sổ để xét tỉnh tiếp theo
  397.     for (int m=0;m<MaxM;m++) {
  398.         for (int mask=0;mask<MASK(Log);mask++) {
  399.             if (BIT(mask,0) && f[pos][m][mask] < INF) minimize(f[pos+1][m][mask>>1],f[pos][m][mask]);
  400.         }
  401.     }
  402. }
  403.  
  404. void sol() {
  405.     // Quy hoạch động bitmask, duyệt theo ý tưởng đã nêu
  406.     for (int x=0;x<N;x++) {
  407.         for (int m=0;m<MaxM;m++) {
  408.             for (int mask=0;mask<MASK(Log);mask++) {
  409.                 if (BIT(mask,0) || f[x][m][mask] >= INF) continue;
  410.                 Push(x,m,mask,{x}); // tỉnh x không sáp nhập
  411.                 for (int y:Edge[x]) {
  412.                     if (y <= x) continue;
  413.                     Push(x,m,mask,{x,y}); // tỉnh x sáp nhập với 1 tỉnh
  414.  
  415.                     // Tỉnh x sáp nhập với 2 tỉnh
  416.                     for (int z:Edge[y]) {
  417.                         if (z <= x) continue;
  418.                         Push(x,m,mask,{x,y,z});
  419.                     }
  420.                     for (int z:Edge[x]) {
  421.                         if (z <= x || z == y) continue;
  422.                         Push(x,m,mask,{x,y,z});
  423.                     }
  424.                 }
  425.             }
  426.         }
  427.         if (x == N - 1) continue;
  428.         // Cập nhật cửa sổ tiếp theo
  429.         Update_To_Next_Province(x);
  430.     }
  431.     // Đặt S = sumGRDP^2
  432.     for (int i=0;i<N;i++) sumGRDP += GRDP[i];
  433.     int S = SQR(sumGRDP);
  434.  
  435.     int M = 0; // Lượng tỉnh sao cho phương án tối ưu nhất
  436.     for (int i=0;i<MaxM;i++) {
  437.         if (f[N-1][i][1] >= INF) continue; // Nếu trường hợp số tỉnh là i không có phương án thì bỏ qua
  438.         if (M == 0) M = i; // Tạo cho M giá trị ban đầu
  439.  
  440.         // Lấy sổ lượng tối ưu cho hàm mục tiêu giữa M và i
  441.         if (1LL*(i*f[N-1][i][1]-S)*SQR(M) < 1LL*(M*f[N-1][M][1]-S)*SQR(i)) {
  442.             M = i;
  443.         }
  444.     }
  445.  
  446.     // Truy vết
  447.     int pos = N-1;
  448.     int mask = 1;
  449.     while (M != 0) {
  450.         if (trace[pos][M][mask] == 0) {
  451.             pos--;
  452.             mask = mask << 1 | 1;
  453.         }
  454.         else {
  455.             int tmpp = trace[pos][M][mask];
  456.             for (int i=0;i<Log;i++) {
  457.                 if (BIT(tmpp,i)) {
  458.                     cout << Real_ID[i+pos] << ' ';
  459.                     mask ^= MASK(i);
  460.                 }
  461.             }
  462.             M--;
  463.             cout << '\n';
  464.         }
  465.     }
  466. }
  467.  
  468. int main() {
  469. //    freopen("YeuCau_6_MoTa.out","w",stdout);
  470.     prepare();
  471.     sol();
  472. }
  473.  
Success #stdin #stdout 2.65s 1132452KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
31 11 
12 0 27 
58 49 4 
19 6 60 
37 56 
57 
7 51 
9 1 
16 8 
34 18 
30 41 
15 
10 43 
32 20 
45 46 
48 55 14 
24 44 
39 
17 50 
62 42 
36 33 
38 40 54 
59 61 
52 22 28 
29 23 
3 53 
13 21 
47 25 26 
35 2 5
https://ideone.com/7xgzwZ
language:
C++ (gcc 8.3)
created:
14 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!