我说这题怎么看着觉得怪怪的。。。
PoPoQQQ给出了解答："给定一个有向图，与起点和终点相连的边只能走一次，剩下的边可以走无数次，问起点到终点可以走多少个人"
题目翻译错了233
好了，那不就是裸的网络流了吗？
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 ", Dinic()); 95 return 0; 96 }