我以后！一定！好好读题！（流下悲伤的泪水）

为了避免更多小可爱误解这道题的题意

我重新复述一遍这个题的题意TAT

我们现在有n道题并且每道题有p个属性可以归属 共计k个属性 要求对于每一种属性选出ai道题

首先一道题只能归属一个属性 所有属性之间互相独立

TAT

我在来偷偷说说我读的版本。。。

每一道题选了对于他所属的p个属性都有1的贡献 一共要选m道题 问你方案TAT

我死活建不出模来然后一看题解这玩意怎么不大对劲啊。。。

然后发现我读错了题QAQ

一个爆哭呜呜呜

 

所以对于正确的题意来说，建模非常简单啦。

我们对每一道题可以向他的所有属性连流量为1的边，因为每道题只能选择一次所以源点向每道题连流量为1的边。最后因为每个属性的选题数目已经给出所以直接向t连流量为ai的边即可。

最后跑最大流看是否满足选出的题数为m就可以了

方案直接枚举每个点然后看流空即可QwQ

附代码。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define inf 20021225#define ll long long#define mxn 1000001using namespace std;struct edge{int to,lt,f;}e[mxn<<1];int in[mxn],cnt=1,dep[mxn],s,t;void addedge(int x,int y,int f){	e[++cnt].to=y;e[cnt].lt=in[x];e[cnt].f=f;in[x]=cnt;	e[++cnt].to=x;e[cnt].lt=in[y];e[cnt].f=0;in[y]=cnt;}queue
         
           que;bool bfs(){ while(!que.empty()) que.pop(); memset(dep,0,sizeof(dep)); dep[s]=1;que.push(s); while(!que.empty()) { int x=que.front();que.pop(); for(int i=in[x];i;i=e[i].lt) { int y=e[i].to; if(!dep[y]&&e[i].f) { dep[y]=dep[x]+1; if(y==t) return 1; que.push(y); } } } return 0;}int dfs(int x,int flow){ if(x==t||!flow) return flow; int cur=flow; for(int i=in[x];i;i=e[i].lt) { int y=e[i].to; if(dep[y]==dep[x]+1&&e[i].f) { int tmp=dfs(y,min(cur,e[i].f)); e[i].f-=tmp;e[i^1].f+=tmp;cur-=tmp; if(!cur) break; } } dep[x]=-1; return flow-cur;}int dinic(){ int ans=0; while(bfs()) ans+=dfs(s,inf); return ans;}int w[21];int main(){ int k,n,i,p,a,j,m=0; scanf("%d%d",&k,&n);s=n+k+1;t=s+1; for(i=1;i<=k;i++) scanf("%d",&w[i]),m+=w[i],addedge(i,t,w[i]); for(i=1;i<=n;i++) { addedge(s,i+k,1); scanf("%d",&p); for(j=1;j<=p;j++) { scanf("%d",&a);//printf("***%d %d\n",i+k,a); addedge(i+k,a,1); } } if(dinic()