Advertisement
Guest User

Untitled

a guest
Sep 21st, 2019
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.85 KB | None | 0 0
  1.     #include <bits/stdc++.h>
  2.      
  3.     using namespace std;
  4.      
  5.     #define ff first
  6.     #define ss second
  7.     #define pb push_back
  8.      
  9.     using ll = long long;
  10.     using ii = pair<int, int>;
  11.      
  12.     const int oo = 1e9;
  13.     const int N = 505;
  14.      
  15.     int main(){
  16.         // Min cost matching
  17.         // O(n^2 * m)
  18.         // n == nro de linhas
  19.         // m == nro de colunas
  20.         // n <= m | flow == n
  21.         // a[i][j] = custo pra conectar i a j
  22.      
  23.         double a[N][N];
  24.         int n, m;
  25.      
  26.         scanf("%d", &n);
  27.         m = n;
  28.      
  29.         for(int i = 1; i <= n; i++) {
  30.             for(int j = 1; j <= n; j++) {
  31.                 int x;
  32.                 scanf("%d", &x);
  33.                 a[i][j] = -log(x);
  34.             }
  35.         }
  36.      
  37.         vector<double> u(n + 1), v(m + 1);
  38.         vector<int> p(m + 1), way(m + 1);
  39.         for(int i = 1; i <= n; ++i){
  40.             p[0] = i;
  41.             int j0 = 0;
  42.             vector<double> minv(m + 1 , 1e50);
  43.             vector<char> used(m + 1 , false);
  44.             do{
  45.                 used[j0] = true;
  46.                 int i0 = p[j0],  j1;
  47.                 double delta = 1e50;
  48.                 for(int j = 1; j <= m; ++j)
  49.                     if(! used[j]){
  50.                         double cur = a[i0][j] - u[i0] - v[j];
  51.                         if(cur < minv[j])
  52.                             minv[j] = cur,  way[j] = j0;
  53.                         if(minv[j] < delta)
  54.                             delta = minv[j] ,  j1 = j;
  55.                     }
  56.                 for(int j = 0; j <= m; ++j)
  57.                     if(used[j])
  58.                         u[p[j]] += delta,  v[j] -= delta;
  59.                     else
  60.                         minv[j] -= delta;
  61.                 j0 = j1;
  62.             }while(p[j0] != 0);
  63.      
  64.             do{
  65.                 int j1 = way[j0];
  66.                 p[j0] = p[j1];
  67.                 j0 = j1;
  68.             }while(j0);
  69.         }
  70.      
  71.         // match[i] = coluna escolhida para linha i
  72.         vector<int> match(n + 1);
  73.         for(int j = 1; j <= m; ++j)
  74.             match[p[j]] = j;
  75.      
  76.         int cost = -v[0];
  77.      
  78.         for(int i = 1; i <= n; i++) {
  79.             printf("%d%c", p[i], " \n"[i == n]);
  80.         }
  81.         return 0;
  82.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement