fork download
copy 
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. pair<int, int> edges[300];
  7. int c[300], n;
  8.  
  9. // depend on the underlying matroid M1 
  10. // X: vector 0-1
  11. vector<int> get_matroid_1_circuit(int id, vector<int> &X) {
  12.     for(int elem = 0; elem < n; elem++) if(X[elem] && edges[id].first == edges[elem].first) {
  13.         return {elem};
  14.     }
  15.     return {};
  16. }
  17. // depend on the underlying matroid M2
  18. vector<int> get_matroid_2_circuit(int id, vector<int> &X) {
  19.     for(int elem = 0; elem < n; elem++) if(X[elem] && edges[id].second == edges[elem].second) {
  20.         return {elem};
  21.     }
  22.     return {};
  23. }
  24. // modified to work in O(E) for sets of large edges
  25. pair<vector<int>, vector<int>> dijkstra(vector<vector<pair<int, int>>> &graph) {
  26.     vector<int> reached, parent, dist;
  27.     parent.resize(n + 2, -1);
  28.     reached.resize(n + 2, 0);
  29.     dist.resize(n + 2, 1'000'000'000); 
  30.     dist[n] = 0;
  31.     parent[n] = n;
  32.     while(true) {
  33.         int m = n + 1;
  34.         for(int i = 0; i < n + 2; i++) if(!reached[i] && dist[i] < dist[m] && parent[i] != -1) m = i;
  35.         // m == n + 1 if and only if dist[t] = infinity, t is not reachable or shortest s-t path found
  36.         if(m == n + 1) break;
  37.         for(auto adj: graph[m]) if(dist[adj.first] > dist[m] + adj.second) {
  38.             dist[adj.first] = dist[m] + adj.second;
  39.             parent[adj.first] = m;
  40.         }
  41.         reached[m] = 1;
  42.     }
  43.     return {parent, dist};
  44. }
  45. vector<int> matroid_intersection() {
  46.     // X is a bitmask vector
  47.     vector<int> w1, w2, X;
  48.     vector<vector<pair<int, int>>> exchange_graph;
  49.     int s = n, t = n + 1;
  50.     w1.resize(n);
  51.     w2.resize(n);
  52.     X.resize(n);
  53.     exchange_graph.resize(n + 2);
  54.     for(int i = 0; i < n; i++) {
  55.         w1[i] = c[i];
  56.         w2[i] = 0;
  57.         X[i] = 0;
  58.     }
  59.     while(true) {
  60.         //constructing exchange_graph
  61.         for(int i = 0; i < n + 2; i++) exchange_graph[i].clear();
  62.         for(int y = 0; y < n; y++) if(!X[y]) {
  63.             vector<int> adj_m1 = get_matroid_1_circuit(y, X);
  64.             if(adj_m1.empty()) {
  65.                 exchange_graph[s].push_back({y, w1[y]});
  66.             }
  67.             else {
  68.                 for(auto x: adj_m1) exchange_graph[x].push_back({y, w1[y] - w1[x]});
  69.             } 
  70.             vector<int> adj_m2 = get_matroid_2_circuit(y, X);
  71.             if(adj_m2.empty()) {
  72.                 exchange_graph[y].push_back({t, w2[y]});
  73.             }
  74.             else {
  75.                 for(auto x: adj_m2) exchange_graph[y].push_back({x, w2[y] - w2[x]});
  76.             }
  77.         }
  78.         auto [parent, dist] = dijkstra(exchange_graph);
  79.         // t is not reachable
  80.         if(parent[t] == -1) break;
  81.         //modify the weight function
  82.         for(int i = 0; i < n; i++)  if(dist[i] <= dist[s]) {
  83.             w1[i] = w1[i] - dist[s] + dist[i];
  84.             w2[i] = w2[i] + dist[s] - dist[i];
  85.         } 
  86.         int path = t;
  87.         //augument X along the shortest path with the shortest length
  88.         while(path != s) {
  89.             path = parent[path];
  90.             if(path != s) X[path] ^= 1;
  91.         }
  92.     }
  93.     return X;
  94. }
  95.  
  96. int main() {
  97.     scanf("%d", &n);
  98.     for(int i = 0; i < n; i++) scanf("%d %d %d", &edges[i].first, &edges[i].second, &c[i]);
  99.     vector<int> best = matroid_intersection();
  100.     int sum = 0;
  101.     for(int id = 0; id < n; id++) if(best[id]) sum += c[id];
  102.     printf("%d\n", sum);
  103.     for(int id = 0; id < n; id++) if(best[id]) printf("%d %d\n", edges[id].first, edges[id].second);
  104. }
  105. /*
  106. 8
  107. 1 1 0
  108. 1 2 0
  109. 2 1 0
  110. 2 4 2
  111. 3 2 1
  112. 3 3 0
  113. 4 3 0
  114. 4 4 9
  115. */
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/xGP5Qd
language:
C++ (gcc 8.3)
created:
1 day 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!