PBCWAYS - Trò chơi di chuyển con tốt

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
const int M = 55;
const int N = 11;
const int MN = 2 * M * N;
const int oo = trunc(1e9);
using namespace std;
vector<int> a[MN];
int Q[MN], T[MN];
int c[MN][MN], f[MN][MN];
int m, n, mn, s, t, res;

void Enter() {
    scanf("%d %d", &m, &n);
    int i, j, u, v, in, out, row, col, cnt;
    for(j=1; j<n; j++)
    for(i=1; i<=m; i++) {
        u = (i - 1) * n + j;
        out = u + u + 1;
        col = j + 1;
        scanf("%d", &cnt);
        while (cnt--) {
            scanf("%d", &row);
            v = (row - 1) * n + col;
            in = v + v;
            c[out][in] = oo;
            a[out].push_back(in);
            a[in].push_back(out);
        }
    }
    mn = m * n; s = 0; t = mn + mn + 2;
    //s >>
    for(i=1; i<= mn; i += n) {
        a[s].push_back(i + i);
        a[i + i].push_back(s);
        c[s][i + i] = oo;
    }
    //>> t
    for(i=n; i<= mn; i += n) {
        a[t].push_back(i + i + 1);
        a[i + i + 1].push_back(t);
        c[i + i + 1][t] = oo;
    }
    //in  - out
    for(i=1; i<=m; i++)
    for(j=1; j<=n; j++) {
        u = (i - 1) * n + j;
        in  = u + u; out = in + 1;
        c[in][out] = 1;
        a[in].push_back(out);
        a[out].push_back(in);
    }
}

bool FindPath() {
    int l = 1, r = 1, i, u, v;
    Q[1] = s;
    for(i=1; i<=t; i++) T[i] = 0;
    while (l <= r) {
        u = Q[l++];
        for(i=0; i<a[u].size(); i++) {
            v = a[u][i];
            if (T[v] == 0 && c[u][v] > f[u][v]) {
                Q[++r] = v;
                T[v] = u;
                if (v == t) return true;
            }
        }
    }
    return false;
}

void IncFlow() {
    int v = t, delta = oo, u;
    while (v != s) {
        u = T[v];
        delta = min(delta, c[u][v] - f[u][v]);
        v = u;
    }
    v = t;
    while (v != s) {
        u = T[v];
        f[u][v] += delta;
        f[v][u] -= delta;
        v = u;
    }
}

int main()
{
    Enter();
    while (FindPath()) IncFlow();
    for(int i=0; i<a[s].size(); i++)
        res += f[s][a[s][i]];
    printf("%d", res);
    return 0;
}

Download