题意：n(n <= 20)个项目，m(m <= 50)个技术问题，做完一个项目能够有收益profit (<= 1000)，做完一个项目必须解决对应的技术问题，解决一个技术问题须要付出cost ( <= 1000)，技术问题之间有先后依赖关系，求最大收益。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4971

——>>项目必须解决相应的技术问题，技术问题之间也存在依赖，相应闭合图，最大收益相应最大权和。。于是，最大权闭合图，最小割，最大流上场。。

建图：

1）超级源S = n + m, 超级汇T = n + m + 1

2）对于每一个项目i：S -> i (profit[i])

3）对于每一个技术问题i：i + n -> T (cost[i])

4）对于项目 i 必须解决的技术问题 j：i -> j + n (INF)

5）对于技术问题 j 必须先解决的技术问题
i： i + n -> j + n (INF) （这里我认为应为：j + n -> i + n (INF)，这样理解才对，但是对不上例子，提交也WA。。）

然后，Dinic上场。。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using std::queue;

using std::min;

const int MAXN = 20 + 50 + 10;

const int MAXM = 20 + 1000 + 2500 + 50 + 10;

const int INF = 0x3f3f3f3f;

int n, m, sum;

int hed[MAXN];

int cur[MAXN], h[MAXN];

int ecnt;

int S, T;

struct EDGE

{

    int to;

    int cap;

    int flow;

    int nxt;

} edges[MAXM << 1];

void Init()

{

    ecnt = 0;

    memset(hed, -1, sizeof(hed));

    sum = 0;

}

void AddEdge(int u, int v, int cap)

{

    edges[ecnt].to = v;

    edges[ecnt].cap = cap;

    edges[ecnt].flow = 0;

    edges[ecnt].nxt = hed[u];

    hed[u] = ecnt++;

    edges[ecnt].to = u;

    edges[ecnt].cap = 0;

    edges[ecnt].flow = 0;

    edges[ecnt].nxt = hed[v];

    hed[v] = ecnt++;

}

void Read()

{

    int profit, cost, pc, tp;

    scanf("%d%d", &n, &m);

    S = n + m;

    T = n + m + 3;

    for (int i = 0; i < n; ++i)

    {

        scanf("%d", &profit);

        AddEdge(S, i, profit);

        sum += profit;

    }

    for (int i = 0; i < m; ++i)

    {

        scanf("%d", &cost);

        AddEdge(i + n, T, cost);

    }

    for (int i = 0; i < n; ++i)

    {

        scanf("%d", &pc);

        for (int j = 0; j < pc; ++j)

        {

            scanf("%d", &tp);

            AddEdge(i, tp + n, INF);

        }

    }

    for (int i = 0; i < m; ++i)

    {

        for (int j = 0; j < m; ++j)

        {

            scanf("%d", &tp);

            if (tp)

            {

                AddEdge(i + n, j + n, INF);

            }

        }

    }

}

bool Bfs()

{

    memset(h, -1, sizeof(h));

    queue<int> qu;

    qu.push(S);

    h[S] = 0;

    while (!qu.empty())

    {

        int u = qu.front();

        qu.pop();

        for (int e = hed[u]; e != -1; e = edges[e].nxt)

        {

            int v = edges[e].to;

            if (h[v] == -1 && edges[e].cap > edges[e].flow)

            {

                h[v] = h[u] + 1;

                qu.push(v);

            }

        }

    }

    return h[T] != -1;

}

int Dfs(int u, int cap)

{

    if (u == T || cap == 0) return cap;

    int flow = 0, subFlow;

    for (int e = cur[u]; e != -1; e = edges[e].nxt)

    {

        cur[u] = e;

        int v = edges[e].to;

        if (h[v] == h[u] + 1 && (subFlow = Dfs(v, min(cap, edges[e].cap - edges[e].flow))) > 0)

        {

            flow += subFlow;

            edges[e].flow += subFlow;

            edges[e ^ 1].flow -= subFlow;

            cap -= subFlow;

            if (cap == 0) break;

        }

    }

    return flow;

}

int Dinic()

{

    int maxFlow = 0;

    while (Bfs())

    {

        memcpy(cur, hed, sizeof(hed));

        maxFlow += Dfs(S, INF);

    }

    return maxFlow;

}

int main()

{

    int t, kase = 0;

    scanf("%d", &t);

    while (t--)

    {

        Init();

        Read();

        printf("Case #%d: %d\n", ++kase, sum - Dinic());

    }

    return 0;

}