/** * ZADANIE KUL * * Uzyty algorytm znaleziony gdzies w odmetach Dysku: * Znajdowanie maksymalnego skojarzenia o minimalnej wadze ( plik stworzony VII 06r ) */ #include #define INFINITE 100000000 #define MXN 510 using namespace std; int n; int pair_left[MXN] , pair_right[MXN]; int label_left[MXN], label_right[MXN]; int delta[MXN], has_delta[MXN]; int kol[MXN]; int tab[MXN][MXN]; void concatLanes(int x) { int tmp; while (x != -1) { pair_right[x] = has_delta[x]; tmp = pair_left[pair_right[x]]; pair_left[pair_right[x]] = x; x = tmp; } } long long kojarz() { int matching = 0; for (int i = 0; i < n; i++ ) { pair_left [i] = -1; pair_right[i] = -1; label_left [i] = INFINITE; label_right[i] = 0; for (int b = 0; b < n; b++ ) //Get shorter path label_left[i] = min(label_left[i], tab[i][b]); } bool tmp = true; int h, t; while (matching < n) { if (tmp) { h = 0; t = 0; for (int i = 0; i < n; i++ ) { delta [i] = INFINITE; has_delta[i] = -1; if (pair_left[i] == -1) kol[t++] = i; } tmp = false; } while (h < t && !tmp) { int cur = kol[h++]; for (int i = 0; i < n && !tmp; i++ ) if (pair_left[cur] != i && tab[cur][i] - (label_left[cur] + label_right[i]) < delta[i]) { delta[i] = tab[cur][i] - (label_left[cur] + label_right[i]); has_delta[i] = cur; if (delta[i] == 0) { if (pair_right[i] == -1) { concatLanes(i); matching++; tmp = true; } else kol[t++] = pair_right[i]; } } } if (!tmp) { int _delta = INFINITE; for (int i = 0; i < n; i++ ) if (delta[i] != 0) _delta = min(_delta, delta[i]); for (int i = 0; i < t; i++ ) label_left[kol[i]] += _delta; for (int i = 0; i < n; i++ ) if (delta[i] == 0) label_right[i] -= _delta; else { delta[i] -= _delta; if (delta[i] == 0 && !tmp) { if (pair_right[i] == -1) { concatLanes(i); matching++; tmp = true; } else kol[t++] = pair_right[i]; } } } } long long ret = 0; for (int i = 0; i < n; i++ ) { ret += label_left[i] + label_right[i]; } return ret; } void readData ( ) { int l, N; scanf("%d%d", &n, &l); for ( int i=0; i<=n; ++i ) { for ( int j=0; j<=n; ++j ) { tab [ i ] [ j ] = 0; } } for (int i=0; i=0; --pos ) { int team; scanf ( "%d", &team ); --team; //cout << pos << endl; for ( int less=pos-1; less>=0; --less ) { tab [ team ] [ less ] += pos - less; } for ( int less=pos+1; less