fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FNAME "RESCUE"
  3. using namespace std;
  4. typedef long long ll;
  5. const int MAXN = (int)505;
  6. const int LIM = (int)1e6 + 1;
  7. const long long MOD = (long long)1e13 + 15092007;
  8. #define xd '\n'
  9. #define pii pair<int, int>
  10. #define pll pair<long long, long long>
  11. #define pli pair<long long, int>
  12. #define fi first
  13. #define se second
  14. const long long base = (long long)256;
  15. const long long INF = (long long)1e14;
  16. template<class X, class Y> bool minimize(X &a, Y b) {if(a>b){a=b;return true;}return false;};
  17. template<class X, class Y> bool maximize(X &a, Y b) {if(a<b){a=b;return true;}return false;};
  18.  
  19. void HuuThien() {
  20.     ios_base::sync_with_stdio(0);
  21.     cin.tie(0); cout.tie(0);
  22.     if (fopen(FNAME".inp", "r")) {
  23.         freopen(FNAME".inp", "r", stdin);
  24.         freopen(FNAME".out", "w", stdout);
  25.     } 
  26. }
  27.  
  28. int n, k;
  29. vector<vector<long long>> grid;
  30. bool visX[MAXN], visY[MAXN];
  31. vector<long long> lx, ly;
  32. vector<long long> slack;
  33. vector<long long> matchU, matchV;
  34.  
  35. bool dfs(int u) {
  36.     visX[u] = true;
  37.  
  38.     for(int v = 1; v <= n ; v++) {
  39.         if(visY[v]) continue;
  40.  
  41.         long long delta = lx[u] + ly[v] - grid[u][v];
  42.         if(delta == 0) {
  43.             visY[v] = true;
  44.             if(!matchV[v] or dfs(matchV[v])) {
  45.                 matchV[v] = u;
  46.                 matchU[u] = v;
  47.                 return true;
  48.             }
  49.         } else {
  50.             slack[v] = min(slack[v], delta);
  51.         }
  52.     }
  53.  
  54.     return false;
  55. }
  56.  
  57. void Hungarian() {
  58.     for(int u = 1; u <= n ; u++) {
  59.         for(int v = 1; v <= n ; v++) {
  60.             lx[u] = max(lx[u], grid[u][v]);
  61.         }
  62.     }
  63.  
  64.     for(int u = 1; u <= n ; u++) {
  65.         for(int v = 1; v <= n ; v++) {
  66.             slack[v] = INF;
  67.         }
  68.  
  69.         while(true) {
  70.             memset(visX, false, sizeof(visX));
  71.             memset(visY, false, sizeof(visY));
  72.  
  73.             if(dfs(u)) break;
  74.  
  75.             long long delta = INF;
  76.  
  77.             for(int v = 1; v <= n ; v++) {
  78.                 if(!visY[v]) {
  79.                     delta = min(delta, slack[v]);
  80.                 }
  81.             }
  82.  
  83.             for(int u = 1; u <= n ; u++) {
  84.                 if(visX[u]) {
  85.                     lx[u] -= delta;
  86.                 }
  87.             }
  88.  
  89.             for(int v = 1; v <= n ; v++) {
  90.                 if(visY[v]) {
  91.                     ly[v] += delta;
  92.                 } else {
  93.                     slack[v] -= delta;
  94.                 }
  95.             }
  96.         }
  97.     }
  98. }
  99.  
  100. void Init() {
  101.     cin >> n >> k;
  102.     slack.assign(n + 1, 0);
  103.     lx.assign(n + 1, 0);
  104.     ly.assign(n + 1 , 0);
  105.     matchU.assign(n + 1, 0);
  106.     matchV.assign(n + 1, 0);
  107.  
  108.     grid.assign(n + 1, vector<long long>(n + 1, 0));
  109.  
  110.     for(int i = 1; i <= n ; i++) {
  111.         for(int j = 1; j <= n ; j++) {
  112.             grid[i][j] = INF;
  113.         }
  114.     }
  115.  
  116.     for(int i = 1; i <= k ; i++) {
  117.         int u, v;
  118.         long long t;
  119.         cin >> u >> v >> t;
  120.         grid[u][v] = min(grid[u][v], t);
  121.     }
  122.  
  123.     for(int i = 1; i <= n ; i++) {
  124.         for(int j = 1; j <= n ; j++) {
  125.             grid[i][j] = -grid[i][j];
  126.         }
  127.     }
  128. }
  129.  
  130. void Solve() {
  131.     Hungarian();
  132.  
  133.     long long res = 0;
  134.     int countNode = 0;
  135.  
  136.     for(int u = 1; u <= n ; u++) {
  137.         if(matchU[u]) {
  138.             countNode++;
  139.             res -= grid[u][matchU[u]];
  140.         }
  141.     }
  142.  
  143.     cout << (countNode == n ? res : -1);
  144. }
  145.  
  146. signed main() {
  147.     HuuThien();
  148.     Init();
  149.     Solve();
  150. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/sF4s9Y
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!