Noor_dinic.cpp

#include <bits/stdc++.h>

using namespace std;

#define INF 2000000000

const int MAX_E=60003;
const int MAX_V=1000;
int ver[MAX_E],cap[MAX_E],nx[MAX_E],last[MAX_V],ds[MAX_V],st[MAX_V],now[MAX_V],edge_count,S,T;

inline void reset()
{
    memset(nx,-1,sizeof(nx));
    memset(last,-1,sizeof(last));
    edge_count=0;
}
inline void addedge(const int v,const int w,const int capacity,const int reverse_capacity)
{
    ver[edge_count]=w; cap[edge_count]=capacity; nx[edge_count]=last[v]; last[v]=edge_count++;
    ver[edge_count]=v; cap[edge_count]=reverse_capacity; nx[edge_count]=last[w]; last[w]=edge_count++;
}
inline bool bfs()
{
    memset(ds,-1,sizeof(ds));
    int a,b;
    a=b=0;
    st[0]=T;
    ds[T]=0;
    while (a<=b)
    {
        int v=st[a++];
        for (int w=last[v];w>=0;w=nx[w])
        {
            if (cap[w^1]>0 && ds[ver[w]]==-1)
            {
                st[++b]=ver[w];
                ds[ver[w]]=ds[v]+1;
            }
        }
    }
    return ds[S]>=0;
}
int dfs(int v,int cur)
{
    if (v==T) return cur;
    for (int &w=now[v];w>=0;w=nx[w])
    {
        if (cap[w]>0 && ds[ver[w]]==ds[v]-1)
        {
            int d=dfs(ver[w],min(cur,cap[w]));
            if (d)
            {
                cap[w]-=d;
                cap[w^1]+=d;
                return d;
            }
        }
    }
    return 0;
}
inline int dinic()
{
    int res=0;
    while (bfs())
    {
        for (int i=0;i<MAX_V;i++) now[i]=last[i];
        while (1)
        {
            int tf=dfs(S,INF);
            res+=tf;
            if (!tf) break;
        }
    }
    return res;
}


int main()
{
    //freopen("input.txt","r",stdin);
    int cases;
    scanf("%d", &cases);
    int caseno = 0;
    while(cases--){
        reset();
        int n;
        scanf("%d", &n);
        int arr[n+1];
        for(int i=1; i<=n; i++){
            scanf("%d", &arr[i]);
            addedge(i, i+n, arr[i], 0);
            //cout << i << " " << i+n << " " << arr[i] << endl;
        }
        int m;
        scanf("%d", &m);
        for(int i=0; i<m; i++){
            int u, v, c;
            scanf("%d %d %d", &u, &v, &c);
            u = u+n;
            addedge(u, v, c, 0);
            //cout << u << " " << v << " " << c << endl;
        }
        int b, d;
        scanf("%d %d", &b, &d);
        for(int i=0; i<b; i++){
            int val;
            scanf("%d", &val);
            addedge(0, val, 10000, 0);
            //cout << 0 << " " << val << " " << 10000 << endl;
        }
        for(int i=0; i<d; i++){
            int val;
            scanf("%d", &val);
            addedge(val+n, 2*n+1, 10000, 0);
            //cout << val << " " << 2*n+1 << " " << 10000 << endl;
        }
        S = 0, T = 2*n+1;
        printf("Case %d: %d\n", ++caseno, dinic());
    }
}