完善程序(单选题,每题3分,共计30分)

1.给一个矩阵N* M,给你第i行1的个数和位置，让你选些行精确覆盖 M列(精确覆盖:每列有且只有1个1)。

例如:如下的矩阵:

11100001

10001110

10010110

00010010

00001100

就包含了这样一个集合(第1,4,5行)。

Input

多组数据,对于每组数据:

第一行两个整数N, M;

楼下来N行，每行开头一个整数x.表示该行上1的个数，接下来x个整数，每个1的位置。

Output

如果有解随意输出组集合，否则输出NO,中间空格隔开。

# include<bits/stdc++.h>


using namespace std;


# define ll long long


# define inf 10000000000


# define N 2005


# define M 2000005


int read()


{


	int x=0,f=1; char ch=getchar();


	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;	ch=getchar();}


	while(ch>='0'&&ch<='9')	{x=x*10+ch-'0';	ch=getchar();}


	return x*f;


}


int n,m;


int h[N],s[N],q[N];


int u[M],d[M],L[M],R[M],C[M],X[M];


void del(int c) //delete ROW C


{


	___(1)___;


	___(2)___;


	for(int i=d[c]; i!=c; i=d[i])


		for(int j=R[i]; j!=i; j=R[j])


			u[d[j]]= u[j],d[u[j]]=d[j],s[C[j]]--;


}


void add(int c)


{


	L[R[c]]= R[L[c]]=c;


	for(int i=u[c]; i!=c; i=u[i])


		for(int j=L[i]; j!=i; j=L[j])


			u[d[j]]= d[u[j]]=j,s[C[j]]++;


}


void link(int r,int c)


{


	static int size=0;size++;


	X[size]=r;C[size]=c;


	s[c]++;


	d[size]= d[c];	u[size]=c;


	u[d[size]]=size;


	d[u[size]]=size;


	if(h[r]==-1)


		h[r]=L[size]=R[size]=size;


	else


	{


		R[size]=R[h[r]];


		L[size]= h[r];


		L[R[size]]=size;


		R[L[size]]= size;


	}


}


bool dance(int k)


{


	if(R[0]=0)


	{


		printf("%d" ,k);


		for(int i=1; i<=k; i++)


			printf(" %d",X[q[i]]);


		puts("");


		return 1;


	}


	int mn=inf,c;


	for(int i= R[0]; i; i=R[i])


		if(s[i]<mn) mn=s[i],c=i;


	___(3)___;


	for(int i=d[c]; i!=c; i=d[i])


	{


		q[k+1]=i;


		for(int j=R[i]; j!=i; j=R[j]) ___(4)___;


		if(dance(k+1)) return 1;


		for(int j=L[i]; j!=i; j=L[j]) ___(5)___;


	}


	add(c);


	return 0;


}


int main()


{


	while(scanf("%d%d",&n,&m)!=EOF)


	{


		for(int i=0; i<=m; i++)


		{


			d[i]=u[i]=i;


			L[i+1]=i;R[i]=i+1;


			s[i]=0;


		}


		R[m]=0;	size=m;


		int x,y;


		for(int i=1; i<=n; i++)


		{


			h[i]=-1;


			x=read();


			while(x--)


			{


				y=read();


				link(i,y);


			}


		}


		if(!dance(0)) puts("NO");


	}


	return 0;


}

选择题