Поиск максимального паросочетания в задаче "Испорченный паркет" - Алгоритмы - Ответ 7039647

#include <iostream>
#include <vector> 
#include <cstdio>
#include <list>
#include <map>
 
std::vector<int> mt;
std::vector<char> marked;
 
 
bool visit(int vertex, std::list<int> adj) {
    if (marked[vertex]) {
        return false;
    }
 
    marked[vertex] = true;
    
    std::list<int>::iterator it;
    for (it = adj.begin(); it != adj.end(); ++it) {
        if (mt[*it] == -1) {
            mt[*it] = vertex;
            return true;
        }
    }
 
    return false;
}
 
 
int pos(int row, int column, int cols) {
    return row * cols + column;
}
 
 
int main() {
    int rows, cols, aPrice, bPrice;
    int count = 0, flow = 0;
    char ch;
    std::map <int, std::list <int> > adjacency;
    std::vector < std::vector<char> > matrix;
    
    std::cin >> rows >> cols >> aPrice >> bPrice;
    matrix.reserve(rows);
 
    int position, current;
    bool isBlack;
 
    for (int iindex = 0; iindex < rows; ++iindex) {
        for (int jindex = 0; jindex < cols; ++jindex) {
            std::cin >> ch;
            matrix[iindex].push_back(ch);
 
            if (ch == '*') {
                current = pos(iindex, jindex, cols);
                isBlack = (iindex % 2 == 0) ? (jindex % 2 == 0) : (jindex % 2 == 1);
                count++;
 
                if (jindex > 0 && matrix[iindex][jindex-1] == '*') {
                    if (isBlack)
                    {
                        position = pos(iindex, jindex - 1, cols);
                        adjacency[position].push_back(current);
                    }
                    else
                    {
                        position = pos(iindex, jindex - 1, cols);
                        adjacency[current].push_back(position);
                    }
                }
 
                if (iindex > 0 && matrix[iindex-1][jindex] == '*') {
                    if (isBlack)
                    {
                        position = pos(iindex - 1, jindex, cols);
                        adjacency[position].push_back(current);
                    }
                    else
                    {
                        position = pos(iindex - 1, jindex, cols);
                        adjacency[current].push_back(position);
                    }
                }                
            }
        }
    }
 
    if (2 * bPrice <= aPrice) {
        std::cout << count * bPrice;
        return 0;
    }
 
    int vertices = rows * cols;
    mt.assign(vertices, -1);
 
    for (auto outer = adjacency.begin(); outer != adjacency.end(); ++outer) {
        marked.assign(vertices, false);
 
        if (visit(outer->first, outer->second)) {
            flow++;
        }
    }
    
    int total = aPrice * (flow) + (count - 2 * flow) * bPrice;
    std::cout << total;
    return 0;
}