Участник:Kachanov vv/STABARDS

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/STABARDS/

#include <iostream>
#include <vector>
 
using namespace std;
 
const int N = 128;
const int Q = 256;
const int QS = 1024;
 
class Solver {
public:
    Solver(int m, int n) : m(m), n(n) {}
 
    void init() {
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < m; ++j) {
                cin >> mat[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            cin >> gender[i];
        }
        for (int i = 0; i < 2 * n; ++i) {
            for (int t = 0; t <= 1; t++) {
                adj[t][i].clear();
            }
        }
    }
 
    void process() {
        char ch;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                ch = mat[gender[i]][gender[j]];
                if (i != j and ch != 'X') {
                    if (ch == 'C') {
                        adj[0][i].push_back(j + n);
                    } else {
                        adj[1][i + n].push_back(i);
                    }
                }
            }
        }
    }
 
    bool alt_path(int x) {
        if (seen[x] == yes) {
            return false;
        }
        seen[x] = yes;
        for (auto y: adj[0][x]) {
            if (mate[1][y] < 0 or alt_path(mate[1][y])) {
                mate[0][mate[1][y] = x] = y;
                return true;
            }
        }
        return false;
    }
 
    int bpm() {
        head = 0;
        tail = 0;
        cnt = 0;
        for (int x = 0; x < n + n; ++x) {
            q[tail++] = x;
            tail &= (QS - 1);
            ++cnt;
        }
        for (int x = 0; x < n + n; ++x) {
            mate[0][x] = -1;
            mate[1][x] = -1;
        }
        bool flag;
        int val;
        while (true) {
            flag = false;
            ++yes;
            for (int k = cnt; k--;) {
                val = q[head++];
                head &= (QS - 1);
                --cnt;
                if (alt_path(val)) {
                    flag = true;
                } else {
                    q[tail++] = val;
                    tail &= (QS - 1);
                    ++cnt;
                }
            }
            if (!flag)
                break;
        }
        return 2 * n - cnt;
    }
 
    void dump() {
        cout << bpm() << "\n";
    }
 
private:
    int m, n, yes, head, tail, cnt;
    int gender[N], seen[Q], mate[2][Q], q[QS];
    char mat[N][N];
    vector<int> adj[2][Q];
};
 
int main() {
    int m, n;
    cin >> m >> n;
    while (m and n) {
        Solver solver(m, n);
        solver.init();
        solver.process();
        solver.dump();
        cin >> m >> n;
    }
    return 0;
}