fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FNAME "hungarian"
  3. using namespace std;
  4. typedef long long ll;
  5. const int MAXN = (int)1e3 + 5;
  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)1e18;
  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, m;
  29. vector<vector<long long>> grid;
  30.  
  31. struct Hungarian{
  32.     int nX, nY;
  33.     vector<int> matchU, matchV;
  34.     vector<long long> slack;
  35.     vector<long long> lx, ly;
  36.     bool visX[MAXN], visY[MAXN];
  37.  
  38.  
  39.     Hungarian(int N, int M) {
  40.         nX = N, nY = M;
  41.         matchU.assign(nX + 1, 0);
  42.         matchV.assign(nY + 1, 0);
  43.         slack.assign(nY + 1, INF);
  44.         lx.assign(nX + 1, 0);
  45.         ly.assign(nY + 1, 0);
  46.     }
  47.  
  48.     bool dfs(int u) {
  49.         visX[u] = true;
  50.  
  51.         for(int v = 1; v <= nY ; v++) {
  52.             if(visY[v]) continue;
  53.  
  54.             long long delta = lx[u] + ly[v] - grid[u][v];
  55.             if(delta == 0) {
  56.                 visY[v] = true;
  57.                 if(!matchV[v] or dfs(matchV[v])) {
  58.                     matchV[v] = u;
  59.                     matchU[u] = v;
  60.                     return true;
  61.                 }
  62.             } else {
  63.                 slack[v] = min(slack[v], delta);
  64.             }
  65.         }
  66.  
  67.         return false;
  68.     }
  69.  
  70.     void Solve() {
  71.         for(int u = 1; u <= nX ; u++) {
  72.             for(int v = 1; v <= nY; v++) {
  73.                 lx[u] = max(lx[u], grid[u][v]);
  74.             }
  75.         }
  76.  
  77.         for(int u = 1; u <= nX ; u++) {
  78.             for(int v = 1; v <= nY; v++) {
  79.                 slack[v] = INF;
  80.             }
  81.  
  82.             while(true) {
  83.                 memset(visX, false, sizeof(visX));
  84.                 memset(visY, false, sizeof(visY));
  85.  
  86.                 if(dfs(u)) break;
  87.  
  88.                 long long delta = INF;
  89.  
  90.                 for(int v = 1; v <= nY ; v++) {
  91.                     if(!visY[v]) {
  92.                         delta = min(delta, slack[v]);
  93.                     }
  94.                 }
  95.  
  96.                 for(int u = 1; u <= nX ; u++) {
  97.                     if(visX[u]) {
  98.                         lx[u] -= delta;
  99.                     }
  100.                 }
  101.  
  102.                 for(int v = 1; v <= nY; v++) {
  103.                     if(visY[v]) {
  104.                         ly[v] += delta;
  105.                     } else {
  106.                         slack[v] -= delta;
  107.                     }
  108.                 }
  109.             }
  110.         }
  111.     }
  112.  
  113.     void getMatch() {
  114.         long long res = 0;
  115.  
  116.         for(int v = 1; v <= nY ; v++) {
  117.             if(matchV[v]) {
  118.                 res += grid[matchV[v]][v];
  119.             }
  120.         }
  121.  
  122.         cout << res << xd;
  123.  
  124.         for(int u = 1; u <= nX ; u++) {
  125.             cout << u << " " << matchU[u] << xd;
  126.         }
  127.     }
  128. };
  129.  
  130. void Init() {
  131.     cin >> n >> m;
  132.     grid.assign(n + 1, vector<long long>(m + 1, 0));
  133.  
  134.     for(int i = 1; i <= n ; i++) {
  135.         for(int j = 1; j <= m ; j++) {
  136.             cin >> grid[i][j];
  137.         }
  138.     }
  139. }
  140.  
  141. void Solve() {
  142.     Hungarian Mbappe(n, m);
  143.  
  144.     Mbappe.Solve();
  145.     Mbappe.getMatch();
  146. }
  147.  
  148. signed main() {
  149.     HuuThien();
  150.     Init();
  151.     Solve();
  152. }
  153.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/E1obRe
language:
C++ (gcc 8.3)
created:
4 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!