1 /************************************************************** 2     Problem: 2929 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:4 ms 7     Memory:1792 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <cstring>12 #include <algorithm>13  14 using namespace std;15 const int N = 205;16 const int M = N * N;17 const int inf = (int) 1e9;18    19 struct edges{20     int next, to, f;21     edges() {}22     edges(int _n, int _t, int _f) : next(_n), to(_t), f(_f) {}23 } e[M << 1];24  25 int n, m, S, T;26 int tot = 1, first[N];27 int d[N], q[N];28  29 inline int read() {30     int x = 0;31     char ch = getchar();32     while (ch < ‘0‘ || ‘9‘ < ch)33         ch = getchar();34     while (‘0‘ <= ch && ch <= ‘9‘) {35         x = x * 10 + ch - ‘0‘;36         ch = getchar();37     }38     return x;39 }40  41 inline void Add_Edges(int x, int y, int z) {42     e[++tot] = edges(first[x], y, z), first[x] = tot;43     e[++tot] = edges(first[y], x, 0), first[y] = tot;44 }45    46 bool bfs() {47     memset(d, 0, sizeof(d));48     q[1] = S, d[S] = 1;49     int l = 1, r = 1, x, y;50     while (l != r + 1) {51         for (x = first[q[l]]; x; x = e[x].next){52             y = e[x].to;53             if (!d[y] && e[x].f)54                 q[(++r) %= N] = y, d[y] = d[q[l]] + 1;55         }56         (++l) %= N;57     }58     return d[T];59 }60    61 int dinic(int p, int limit) {62     if (p == T || !limit) return limit;63     int x, y, tmp, rest = limit;64     for (x = first[p]; x; x = e[x].next) {65         y = e[x].to;66         if (d[y] == d[p] + 1 && e[x].f && rest) { 67             tmp = dinic(y, min(rest, e[x].f));68             rest -= tmp;69             e[x].f -= tmp, e[x ^ 1].f += tmp;70             if (!rest) return limit;71         }72     }73     if (limit == rest) d[p] = 0;74     return limit - rest;75 }76    77 int Dinic() {78     int res = 0, x;79     while (bfs())80         res += dinic(S, inf);81     return res;82 }83  84 int main() {85     int i, j, x;86     n = read();87     for (i = 1; i < n; ++i) {88         for (j = 1, m = read(); j <= m; ++j) {89             x = read();90             Add_Edges(i, x, i == 1 || x == n ? 1 : inf);91         }92     }93     S = 1, T = n;94     printf("%d\n", Dinic());95     return 0;96 }