建图：s向所有猪圈的第一个顾客连流量为这个猪圈里住的数量，然后对于之后每个来这个猪圈的顾客，由他前一个顾客向他连边权为无穷的边，然后每个顾客向t连流量为这个顾客购买上限的边。然后跑最大流
#include#include #include #include #include using namespace std;const int M=1005,N=105,inf=1e8;;int m,n,a[M],b[N],s,t,h[N],cnt=1,le[N];vector v[M];struct qwe{ int ne,to,v;}e[N*N<<1];int read(){ int r=0,f=1; char p=getchar(); while(p>'9'||p<'0') { if(p=='-') f=-1; p=getchar(); } while(p<='9'&&p>='0') { r=r*10+p-48; p=getchar(); } return r*f;}void add(int u,int v,int w){ cnt++; e[cnt].ne=h[u]; e[cnt].to=v; e[cnt].v=w; h[u]=cnt;}void ins(int u,int v,int w){ add(u,v,w); add(v,u,0);}bool bfs(){ queue q; memset(le,0,sizeof(le)); q.push(s); le[s]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=h[u];i;i=e[i].ne) if(e[i].v>0&&!le[e[i].to]) { le[e[i].to]=le[u]+1; q.push(e[i].to); } } return le[t];}int dfs(int u,int f){ if(u==t||!f) return f; int us=0; for(int i=h[u];i;i=e[i].ne) if(e[i].v>0&&le[e[i].to]==le[u]+1) { int t=dfs(e[i].to,min(e[i].v,f-us)); e[i].v-=t; e[i^1].v+=t; us+=t; } if(us==0) le[u]=0; return us;}int dinic(){ int re=0; while(bfs()) re+=dfs(s,inf); return re;}int main(){ m=read(),n=read(); s=0,t=n+1; for(int i=1;i<=m;i++) a[i]=read(); for(int i=1;i<=n;i++) { int x=read(); for(int j=1;j<=x;j++) { int y=read(); v[y].push_back(i); } b[i]=read(); ins(i,t,b[i]); } for(int i=1;i<=m;i++) if(v[i].size()) { ins(s,v[i][0],a[i]); for(int j=1;j