Pig

wc掉线了，于是颓题解

顾客为什么有钥匙啊

大体思路显然是，建源点$S$向顾客连容量为需求的边，猪圈向汇点$T$连容量为$+\infty$的边，然后顾客与猪圈以某种方式连边，最后的最大流即为答案。

对于顾客与猪圈连边，一种错误的方法是，对每个顾客建一个虚点$P$,每个他能开的猪圈向$P$连容量为$+\infty$的无向边，然后顾客向这个虚点连边。这样是样例也过不去的，错误的原因是，第一个顾客有1,2的钥匙，第二个顾客有1，3的钥匙，并不意味着3的猪一定能换到2上。

考虑对于当前的顾客$i$，求出他可以支配的猪圈集合$S_i$，即可以在之前通过某些方法让他能任意选择的猪圈。首先他直接有钥匙的猪圈显然属于$S_i$.其次，$\forall j<i,,\forall x,y\in A_j,x\in S_i$,必然有$y\in S_i$(即若$S_i\cup A_j\ne\emptyset$,令$S_i=S_i\cap A_j$.令$i$向$S_i$中每个点连边即可。可以std::bitset维护。

时间复杂度理论上界$O(\frac{n^2m}\omega +nm\sqrt{nm}))$,但完全跑不到。在poj上0ms。。。

std::bitset<1011>s[111];
int main()
{
    int n2=read(),n1=read(),S=n1+n2+1,T=S+1,tot=T;
    for(int i=1;i<=n2;++i)adde(n1+i,T,read());
    for(int i=1;i<=n1;++i)
    {
        int l=read();
        while(l--)s[i][read()]=1;
        std::bitset<1011>pos=s[i];
        for(int j=i-1;j;--j)
            if((pos&s[j]).any())pos|=s[j];
        for(int j=1;j<=n2;++j)
            if(pos[j])adde(i,n1+j,INF);
        adde(S,i,read());
    }
    printf("%lld",Dinic(S,T,tot));
    return 0;
}