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