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;
}