Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ff first
- #define ss second
- #define pb push_back
- using ll = long long;
- using ii = pair<int, int>;
- const int oo = 1e9;
- const int N = 505;
- int main(){
- // Min cost matching
- // O(n^2 * m)
- // n == nro de linhas
- // m == nro de colunas
- // n <= m | flow == n
- // a[i][j] = custo pra conectar i a j
- double a[N][N];
- int n, m;
- scanf("%d", &n);
- m = n;
- for(int i = 1; i <= n; i++) {
- for(int j = 1; j <= n; j++) {
- int x;
- scanf("%d", &x);
- a[i][j] = -log(x);
- }
- }
- vector<double> u(n + 1), v(m + 1);
- vector<int> p(m + 1), way(m + 1);
- for(int i = 1; i <= n; ++i){
- p[0] = i;
- int j0 = 0;
- vector<double> minv(m + 1 , 1e50);
- vector<char> used(m + 1 , false);
- do{
- used[j0] = true;
- int i0 = p[j0], j1;
- double delta = 1e50;
- for(int j = 1; j <= m; ++j)
- if(! used[j]){
- double cur = a[i0][j] - u[i0] - v[j];
- if(cur < minv[j])
- minv[j] = cur, way[j] = j0;
- if(minv[j] < delta)
- delta = minv[j] , j1 = j;
- }
- for(int j = 0; j <= m; ++j)
- if(used[j])
- u[p[j]] += delta, v[j] -= delta;
- else
- minv[j] -= delta;
- j0 = j1;
- }while(p[j0] != 0);
- do{
- int j1 = way[j0];
- p[j0] = p[j1];
- j0 = j1;
- }while(j0);
- }
- // match[i] = coluna escolhida para linha i
- vector<int> match(n + 1);
- for(int j = 1; j <= m; ++j)
- match[p[j]] = j;
- int cost = -v[0];
- for(int i = 1; i <= n; i++) {
- printf("%d%c", p[i], " \n"[i == n]);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement