fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5. PROBLEM (in simple words)
  6. -------------------------
  7. There are n locations. Moving all resources from i -> j costs cost[i][j].
  8. You are allowed to move via intermediate locations (i -> x -> j) if cheaper.
  9.  
  10. Goal: After moving, resources should remain in AT MOST k locations (you choose which).
  11. Every other location sends its resources to one of the chosen "hub" locations.
  12. Minimize total cost.
  13.  
  14. Key ideas
  15. ---------
  16. 1) Floyd–Warshall:
  17.    Because intermediate routing is allowed, first convert cost[][] into shortest-path costs.
  18.  
  19. 2) Choose hubs (<= k):
  20.    If we choose a hub set S, then each location i pays:
  21.        min_{h in S} dist[i][h]
  22.    Total cost = sum over all i of that minimum.
  23.  
  24. 3) Exact solution for small n (n <= ~20-22):
  25.    Enumerate all hub sets using bitmasks, but efficiently using DP:
  26.    For each location i, compute bestToSet[mask] = min cost from i to any hub in 'mask'.
  27.    Then accumulate into totalCost[mask] += bestToSet[mask].
  28.  
  29. Complexities
  30. ------------
  31. - Floyd–Warshall: O(n^3)
  32. - Bitmask DP: O(n * 2^n)
  33. - Memory: O(2^n)
  34.  
  35. NOTE:
  36. - This exact approach is feasible only when n is small (typically <= 22).
  37. - If your OA guarantees small n, you can keep the guard.
  38. */
  39.  
  40. int main() {
  41.     ios::sync_with_stdio(false);
  42.     cin.tie(nullptr);
  43.  
  44.     int n, k;
  45.     cin >> n >> k;
  46.  
  47.     const long long INF = (1LL << 62);
  48.  
  49.     // If n is too large, exact bitmask DP is not feasible.
  50.     // If your OA guarantees n <= 20/22, this guard is fine.
  51.     if (n > 22) {
  52.         cout << -1 << "\n";
  53.         return 0;
  54.     }
  55.  
  56.     // If k == 0, you cannot keep resources anywhere (usually not asked, but safe).
  57.     if (k == 0) {
  58.         cout << -1 << "\n";
  59.         return 0;
  60.     }
  61.  
  62.     // Read cost matrix.
  63.     // If your problem uses -1 meaning "no direct transfer", convert it to INF.
  64.     vector<vector<long long>> dist(n, vector<long long>(n));
  65.     for (int i = 0; i < n; i++) {
  66.         for (int j = 0; j < n; j++) {
  67.             long long x;
  68.             cin >> x;
  69.  
  70.             // Common OA convention:
  71.             // if (x == -1) dist[i][j] = INF; else dist[i][j] = x;
  72.             dist[i][j] = x;
  73.         }
  74.     }
  75.  
  76.     // Keeping a location means no move -> cost must be 0 on diagonal.
  77.     for (int i = 0; i < n; i++) dist[i][i] = 0;
  78.  
  79.     // Floyd–Warshall: compute shortest shipping cost between every pair.
  80.     for (int mid = 0; mid < n; mid++) {
  81.         for (int i = 0; i < n; i++) {
  82.             if (dist[i][mid] >= INF / 2) continue; // no point continuing if i->mid is impossible
  83.             for (int j = 0; j < n; j++) {
  84.                 if (dist[mid][j] >= INF / 2) continue; // mid->j impossible
  85.                 long long cand = dist[i][mid] + dist[mid][j];
  86.                 if (cand < dist[i][j]) dist[i][j] = cand;
  87.             }
  88.         }
  89.     }
  90.  
  91.     // If we can keep all locations, we move nothing.
  92.     if (k >= n) {
  93.         cout << 0 << "\n";
  94.         return 0;
  95.     }
  96.  
  97.     int ALL = 1 << n; // number of subsets
  98.  
  99.     // totalCost[mask] = total cost if we keep exactly the hub set 'mask'
  100.     vector<long long> totalCost(ALL, 0);
  101.  
  102.     // bestToSet[mask] will be reused for each location i:
  103.     // bestToSet[mask] = min_{h in mask} dist[i][h]
  104.     vector<long long> bestToSet(ALL);
  105.  
  106.     // Build totalCost by processing each location one-by-one.
  107.     for (int i = 0; i < n; i++) {
  108.         // Empty hub set is invalid; set its cost to INF.
  109.         bestToSet[0] = INF;
  110.  
  111.         // DP over masks:
  112.         // bestToSet[mask] = min(bestToSet[mask without lowest bit], dist[i][lowestBitHub])
  113.         for (int mask = 1; mask < ALL; mask++) {
  114.             int hub = __builtin_ctz((unsigned)mask);     // index of lowest set bit
  115.             int prev = mask & (mask - 1);               // mask with that bit removed
  116.             bestToSet[mask] = min(bestToSet[prev], dist[i][hub]);
  117.         }
  118.  
  119.         // Add this location's cost to each hub set (skip mask=0).
  120.         for (int mask = 1; mask < ALL; mask++) {
  121.             __int128 sum = (__int128)totalCost[mask] + bestToSet[mask];
  122.             totalCost[mask] = (sum > (__int128)INF) ? INF : (long long)sum;
  123.         }
  124.     }
  125.  
  126.     // Answer = minimum totalCost[mask] among masks with popcount(mask) <= k
  127.     long long ans = INF;
  128.     for (int mask = 1; mask < ALL; mask++) {
  129.         if (__builtin_popcount((unsigned)mask) <= k) {
  130.             ans = min(ans, totalCost[mask]);
  131.         }
  132.     }
  133.  
  134.     // If unreachable paths exist and no valid hub set works, ans may remain INF.
  135.     if (ans >= INF / 2) cout << -1 << "\n";
  136.     else cout << ans << "\n";
  137.  
  138.     return 0;
  139. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/sBzbDn
language:
C++14 (gcc 8.3)
created:
2 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!