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