1 #include <iostream>  2 #include <algorithm>  3 #include <cstdio>  4 #include <cstdlib>  5 #include <cstring>  6   7 using namespace std;  8   9 const int N = 128; 10 const int M = 1e5 + 7; 11 const int INF = 0x3f3f3f3f; 12  13 struct Edge{ 14     int v, ne, c, f; 15 }; 16  17 struct Net_Dinic{ 18     Edge e[M]; 19     int q[N], stack[N], head[N], cur[N], dis[N]; 20     bool used[N]; 21      22     int pos, top, stop, flow, S, T; 23      24     bool adde(int u, int v, int c){ 25         //printf("%d -> %d %d\n", u, v, c); 26         e[++pos] = (Edge){v, head[u], c, 0}; 27         head[u] = pos; 28         e[++pos] = (Edge){u, head[v], c, c}; 29         head[v] = pos; 30     } 31      32     void init(int s, int t){ 33         S = s; 34         T = t; 35         memset(head, 0, sizeof(head)); 36         flow = top = 0; 37         pos = 1; 38     } 39      40     bool number(){ 41         //printf("Number\n"); 42         memset(dis, 0x3f, sizeof(dis)); 43         memset(used, 0, sizeof(used)); 44         int p1, p2; 45         q[p1 = p2 = 1] = S; 46         used[S] = true; 47         dis[S] = 0; 48         while (p1 <= p2){ 49             int u = q[p1++]; 50             for (int i = head[u]; i; i = e[i].ne){ 51                 int v = e[i].v; 52                 if (!used[v] && e[i].c > e[i].f){ 53                     q[++p2] = v; 54                     dis[v] = dis[u] + 1; 55                     used[v] = true; 56                 } 57             } 58         } 59         memcpy(cur, head, sizeof(head)); 60         return dis[T] != INF; 61     } 62      63     bool find(int u){ 64         if (u == T){ 65             int cut = INF; 66             for (int i = 1; i <= top; ++i) 67                 cut = min(cut, e[stack[i]].c - e[stack[i]].f); 68             for (int i = top; i; --i){ 69                 e[stack[i]].f += cut; 70                 e[stack[i] ^ 1].f -= cut; 71                 if (e[stack[i]].c == e[stack[i]].f) 72                     stop = i; 73             } 74             flow += cut; 75             return true; 76         } 77         for (int &i = cur[u]; i; i = e[i].ne){ 78             int v = e[i].v; 79             if (e[i].c > e[i].f && dis[v] == dis[u] + 1){ 80                 stack[++top] = i; 81                 if (find(v) && stop != top){ 82                     --top; 83                     return true; 84                 } 85                 --top; 86             } 87         } 88         return false; 89     } 90      91     int maxflow(){ 92         while (number()) 93             find(S); 94         return flow; 95     } 96 }net; 97  98 int main(){ 99     int T, n, m, s, t, x, y, sum;100     scanf("%d", &T);101     for (int Test = 1; Test <= T; ++Test){102         scanf("%d%d", &n, &m);103         s = n + m + 1;104         t = s + 1;105         net.init(s, t);106         107         sum = 0;108         for (int i = 1; i <= n; ++i){109             scanf("%d", &x);110             net.adde(s, i, x);111             sum += x;112         }113         114         for (int i = 1; i <= m; ++i){115             scanf("%d", &x);116             net.adde(i + n, t, x);117         }118         119         for (int i = 1; i <= n; ++i){120             scanf("%d", &y);121             while (y--){122                 scanf("%d", &x);123                 net.adde(i, x + n + 1, INF);124             }125         }126         127         for (int i = 1; i <= m; ++i)128             for (int j = 1; j <= m; ++j){129                 scanf("%d", &x);130                 if (x == 1)131                     net.adde(i + n, j + n, INF);132             }133         int ans = net.maxflow();134         printf("Case #%d: %d\n", Test, sum - ans);135     }136     return 0;137 }