Description

There's a company with several projects to be done. Finish a project will get you profits. However, there are some technical problems for some specific projects. To solve the problem, the manager will train his employee which may cost his budget. There may be dependencies between technical problems, for example, A requires B means you need to solve problem B before solving problem A. If A requires B and B requires A, it means that you should solve them at the same time. You can select which problems to be solved and how to solve them freely before finish your projects. Can you tell me the maximum profit?
 

Input

The first line of the input is a single integer T(<=100) which is the number of test cases.

Each test case contains a line with two integer n(<=20) and m(<=50) which is the number of project to select to complete and the number of technical problem.

Then a line with n integers. The i-th integer(<=1000) means the profit of complete the i-th project.

Then a line with m integers. The i-th integer(<=1000) means the cost of training to solve the i-th technical problem.

Then n lines. Each line contains some integers. The first integer k is the number of technical problems, followed by k integers implying the technical problems need to solve for the i-th project.

After that, there are m lines with each line contains m integers. If the i-th row of the j-th column is 1, it means that you need to solve the i-th problem before solve the j-th problem. Otherwise the i-th row of the j-th column is 0.
 

Output

For each test case, please output a line which is "Case #X: Y ", X means the number of the test case and Y means the the maximum profit.
 

Sample Input

4 2 3 10 10 6 6 6 2 0 1 2 1 2 0 1 0 1 0 0 0 0 0 2 3 10 10 8 10 6 1 0 1 2 0 1 0 1 0 0 0 0 0 2 3 10 10 8 10 6 1 0 1 2 0 1 0 0 0 0 0 0 0 2 3 10 10 8 10 6 1 0 1 2 0 0 0 1 0 0 0 0 0
 

Sample Output

Case #1: 2 Case #2: 4 Case #3: 4 Case #4: 6
 

题意：完成课题能赚钱，每个课题需要完成一些问题，问题需要花钱，问题之间有依赖关系，问最多赚多少钱。

下午上实验百思不得其解，晚上听见后面学弟说了一句最大权闭合图，唤醒了我尘封的记忆：

最大权闭合图 hdu 3879 Base Station 有模板！

然后纠结于如何表示依赖关系，自以为是的拆点限制了，其实不对，只在原图右侧的m个点连边就可以了== 
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mm=220005;
const int mn=22222;
const int oo=1000000000;
int node,src,dest,edge;
int reach[mm],flow[mm],nxt[mm];
int head[mn],work[mn],dis[mn],q[mn];
inline int min(int a,int b)
{
    return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
    node=_node,src=_src,dest=_dest;
    memset(head,-1,sizeof(head));
    edge=0;
}
inline void addedge(int u,int v,int c1)
{
    reach[edge]=v,flow[edge]=c1,nxt[edge]=head[u],head[u]=edge++;
    reach[edge]=u,flow[edge]=0,nxt[edge]=head[v],head[v]=edge++;
}
bool Dinic_bfs()
{
    int i,u,v,l,r=0;
    for(i=0;i<node;++i)dis[i]=-1;
    dis[q[r++]=src]=0;
    for(l=0;l<r;++l)
        for(i=head[u=q[l]];i>=0;i=nxt[i])
            if(flow[i]&&dis[v=reach[i]]<0)
            {
                dis[q[r++]=v]=dis[u]+1;
                if(v==dest)return 1;
            }
    return 0;
}
int Dinic_dfs(int u,int exp)
{
    if(u==dest)return exp;
    for(int &i=work[u],v,tmp;i>=0;i=nxt[i])
        if(flow[i]&&dis[v=reach[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
        {
            flow[i]-=tmp;
            flow[i^1]+=tmp;
            return tmp;
        }dis[u]--;
    return 0;
}
int Dinic_flow()
{
    int i,ret=0,delta;
    while(Dinic_bfs())
    {
        for(i=0;i<node;++i)work[i]=head[i];
        while(delta=Dinic_dfs(src,oo))ret+=delta;
    }
    return ret;
}
int main()
{
 //   freopen("cin.txt","r",stdin);
    int t,n,m,cas=1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        prepare(n+m+2,0,n+m+1);
        int count=0;
        for(int i=1;i<=n;i++)
        {
            int c;
            scanf("%d",&c);
            addedge(src,i,c);
            count+=c;
        }
        for(int i=1;i<=m;i++)
        {
            int c;
            scanf("%d",&c);
            addedge(n+i,dest,c);
        }
        for(int i=1;i<=n;i++)
        {
            int k;
            scanf("%d",&k);
            while(k--)
            {
                int c;
                scanf("%d",&c);
                addedge(i,n+c+1,oo);
            }
        }
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=m;j++)
            {
                int c;
                scanf("%d",&c);
                if(c)addedge(n+i,n+j,oo);
            }
        }
        printf("Case #%d: %d\n",cas++,count-Dinic_flow());
    }
    return 0;
}