最大流。。很好构图。。实际上不用上下界的。。
源到每个学生联一条容量1的边。。学生到每个能去的学校连一条容量1的边。。学校到汇连一条容量为2的边。。然后判断流量是否是学校的2倍就OK了。。。
Code。。
#include<iostream>
#include<string.h>
using namespace std;
const int maxn=200+10,maxk=200+10,maxV=maxn+maxk,inf=~0U>>1;
int vs,vt;
int n,k;
struct edge
{
int t,c;
edge*next,*op;
edge(int t,int c,edge*n):t(t),c(c),next(n){}
}*E[maxV];
int H[maxV],VH[maxV];
void addedge(int s,int t,int c)
{
E[s]=new edge(t,c,E[s]);
E[t]=new edge(s,0,E[t]);
E[s]->op=E[t];E[t]->op=E[s];
}
inline int stu(int n){return n;}
inline int sch(int n){return n+maxn;}
int aug(int no,int m)
{
if(no==vt) return m;
int l=m;
for(edge*i=E[no];i;i=i->next) if(i->c&&H[i->t]+1==H[no])
{
int d=aug(i->t,min(i->c,l));
l-=d;i->c-=d;i->op->c+=d;
if(H[vs]==n||l==0) return m-l;
}
int minh=n;            for(edge*i=E[no];i;i=i->next) if(i->c)
if(H[i->t]+1<minh) minh=H[i->t]+1;
if(!–VH[H[no]]) H[vs]=n;else ++VH[H[no]=minh];
return m-l;
}
void init()
{
cin>>n>>k;vs=0;vt=maxV-1;
for(int i=1;i<=n;i++)
{
int t,s;cin>>t;
addedge(vs,stu(i),1);
for(int j=0;j<t;j++)
{
cin>>s;addedge(stu(i),sch(s),1);
}
}   
n+=2+k;
for(int i=1;i<=k;i++)
addedge(sch(i),vt,2);
memset(H,0,sizeof(H));
memset(VH,0,sizeof(VH));
VH[0]=n;
}
void solve()
{   
int ans=0;
while(H[vs]<n) ans+=aug(vs,inf);   
if(ans<2*k)
cout<<"NOn";
else
{
cout<<"YESn";int ans[maxn];
for(int i=1;i<=k;i++)
{
int num=0;           
for(edge*j=E[sch(i)];j;j=j->next)
if(j->t!=vt&&j->c==1)
{
ans[num++]=j->t;
}
cout<<num;
for(int o=0;o<num;o++)
cout<<" "<<ans[o];
cout<<endl;
}
}
}
int main()
{
init();
solve();
}