9 контест Ярику

#include <iostream>
#include <vector>

using namespace std;

class Task {

    int n, m;
    int free_cells = 0;
    vector<vector<int>> g;
    vector<int> parasoch;
    vector<bool> used;
    int parasoch_cnt = 0;

    vector<string> s;
public:
    Task(int _n, int _m) {
        n = _n;
        m = _m;
        g.resize(n * m);
        used.resize(n * m);
        parasoch.resize(n * m, -1);
        s.resize(n);


    }

    void read_graph(){
        for (auto &i: s) {
            cin >> i;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (s[i][j] == '.')
                    continue;
                free_cells++;
                if ((i + j) % 2)
                    continue;

                if (j && (s[i][j - 1] == '*'))
                    g[i * m + j].push_back(i * m + j - 1);

                if ((j < m - 1) && (s[i][j + 1] == '*'))
                    g[i * m + j].push_back(i * m + j + 1);

                if (i && (s[i - 1][j] == '*'))
                    g[i * m + j].push_back((i - 1) * m + j);

                if ((i < n - 1) && (s[i + 1][j] == '*'))
                    g[i * m + j].push_back((i + 1) * m + j);
            }
        }
    }

    bool dfs(int v) {
        if (used[v])
            return false;
        used[v] = true;
        for (int i = 0; i < g[v].size(); i++) {
            int to = g[v][i];
            if (parasoch[to] == -1 || dfs(parasoch[to])) {
                parasoch[to] = v;
                return true;
            }
        }
        return false;
    }

    void solve() {




        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if ((i + j) % 2 == 1)
                    continue;
                used.assign(n * m, false);
                dfs(i * m + j);
            }
        }
        for (int i = 0; i < n * m; i++) {
            if (parasoch[i] != -1) {
                parasoch_cnt++;
            }
        }

    }

    void print_result(int a, int b){
        if (2 * b <= a) {
            cout <<  free_cells * b;
        }
        else{
            cout << parasoch_cnt * a + (free_cells - 2 * parasoch_cnt) * b;
        }
    }
};

int main() {
    int n, m, a, b;
    cin >> n >> m >> a >> b;

    Task t(n, m);
    t.read_graph();
    t.solve();
    t.print_result(a, b);

    return 0;
}

// 2

#include <iostream>
#include <vector>

using namespace std;

class Task {

    int n;
    int free_cells = 0;
    vector<vector<int>> g;
    vector<int> parasoch;
    vector<bool> used;

    vector<string> s;
    string sister;
    int is_ok = true;

public:
    Task(int _n) {
        n = _n;
        g.resize(n);
        used.resize(n);
        parasoch.resize(n, -1);
        s.resize(n);
    }

    void read_graph() {
        cin >> sister;

        for (int i = 0; i < s.size(); i++)
            cin >> s[i];

        for (int i = 0; i < sister.size(); i++){
            for (int j = 0; j < n; j++){
                for (int k = 0; k < 6; k++){
                    if (sister[i] == s[j][k]){
                        g[j].emplace_back(i);
                    }
                }
            }
        }
    }

    bool dfs(int v) {
        if (used[v])
            return false;
        used[v] = true;
        for (int i = 0; i < g[v].size(); i++) {
            int to = g[v][i];
            if (parasoch[to] == -1 || dfs(parasoch[to])) {
                parasoch[to] = v;
                return true;
            }
        }
        return false;
    }

    void solve() {


        for (int i = 0; i < n; i++) {
            used.assign(n, false);
            dfs(i);
        }


        for (int i = 0; i < n; i++) {
            if (parasoch[i] == -1) {
                is_ok = false;
            }
        }

    }

    void print_result() {
        if (is_ok){
            cout << "YES" << endl;
            for (int i = 0; i < s.size(); i++){
                cout << parasoch[i] + 1 << ' ';
            }
        }
        else
            cout << "NO";
    }

};

int main() {
    int n;
    cin >> n;

    Task t(n);
    t.read_graph();
    t.solve();
    t.print_result();

    return 0;
}