3 科技节
(scifest.pas/.c/.cpp)
【问题描述】
一年一度的科技节即将到来。同学们报名各项活动的名单交到了方克顺校长那，结果校长一看皱了眉头：这帮学生热情竟然如此高涨，每个人都报那么多活动，还要不要认真学习了？！这样不行！……于是，校长要求减少一些活动，使每位学生只能参加一项（一名同学要参加某活动，必须已报名且该活动未被去掉）。当然，他也不希望哪位同学因此不能参加任何活动。他想知道自己的方案能否实行。
【输入】
输入文件名为scifest.in。
输入数据包括多组。
对于每组数据：
第一行两个正整数n和m，分别表示活动数和学生数。
接下来n行，每行m个为0或1的数。第i+1行第j列的数若为1，表示j同学报名参加活动i，否则表示j同学没有报名参加活动i。
【输出】
输出文件名为scifest.out。
对于每组数据输出一行，若校长方案可行则输出“Yes”，否则输出“No”。（均不包括引号）
【输入输出样例】
|
scifest.in |
scifest.out |
|
3 3 0 1 0 0 0 1 1 0 0 4 4 0 0 0 1 1 0 0 0 1 1 0 1 0 1 0 0 |
Yes No |
【数据范围】
对于20%的数据，n≤10，m≤200，数据组数≤10；
对于60%的数据，n≤16，m≤300，数据组数≤100；
对于100%的数据，n≤16，m≤300，数据组数≤1,000。
解题报告：
这道题好像是我在这套题里唯一做了的，用了一个搜索，每次去找只选了唯一活动的学生，做标记，没有唯一的就找哪一个活动参与的人最少，然后删去。再重复刚才的步骤，直到所有未被删的都是唯一标记，若不是，就为No.我觉得并没有错，可是，可是，我把n和m看反了。。输入都是对的，后来进入搜索就忘了，于是，全错，还有，我连Yes，No 都输出的是YES NO ，能不全错吗？.......
那天因为时间原因，我也没有去调试改错，看一下我原程序的错误，这里便给一个标程的解释吧。
标程也是用的搜索，只不过它是记录的选中的活动及其人数，再加上 位运算 的使用，十分巧妙。位运算也是以前讲过的，复习一下：
&：0 1 0 1 | ：0 1 0 1 ^: 0 1 0 1
1 1 0 0 1 1 0 0 1 1 0 0
0 1 0 0 1 1 0 1 1 0 0 1
下面是对标程中的一些难理解的代码的解释：
1 int x[20][10],h[20];
x[20][10]:最大二进制数31位，此处有300个学生，把每一项活动的300个用10组二进制数记录其 1 的位置。
1 if (a==1) 2 { 3 x[i][j/31]+=1<<(j%31); 4 h[i]++; 5 }
1、x[i][j/31]：第 i 个项目 第 k 组 ，如果参加。一个二进制数为32位，一位符号位，/31 即这个1 在第几组 上,j %31 即这一组的第几位上是 1。
1 for ( i=0;i<10;i++) 2 { 3 if ((s[i]&x[p][i])>0) break; 4 t[i]=s[i]|x[p][i]; 5 }
这里是选择活动时的操作：s[i]是已经选了的活动。&：如果s[i]与x[p][i]上的1 有重复，（如：0 1 0 1&1 1 0 0），则说明一个人有两个活动了，break;
| :如果选这个活动这个人本来没有选的，s[i]这一位上为0，则这项活动可以选（如：0 1 0 1|1 0 0 0 [第二行的1可以选]）
另外，还要按照活动的参与人数进行排序，人多的先选。
下面是完整代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 using namespace std; 6 int n,m; 7 int x[20][10],h[20]; 8 bool yes=0; 9 void work() 10 { 11 memset(x,0,sizeof (x)); 12 for (int i=0;i<n;i++) 13 { 14 h[i]=0; 15 for (int j=0;j<m;j++) 16 { 17 int a; 18 scanf("%d",&a); 19 if (a==1) 20 { 21 x[i][j/31]+=1<<(j%31); 22 h[i]++; 23 } 24 } 25 } 26 int k; 27 for (int i=0;i<n-1;i++) //? n-1 28 for (int j=i+1;j<n;j++) 29 { 30 if (h[i]<h[j]) 31 { 32 k=h[i];h[i]=h[j];h[j]=k; 33 for (int t=0;t<10;t++) 34 { 35 int u=x[i][t];x[i][t]=x[j][t];x[j][t]=u; 36 } 37 } 38 } 39 } 40 void doit(int p,int s[10],int have) 41 { 42 if (p==n) 43 { 44 if (have==m) yes=1; 45 return ; 46 } 47 int t[10],i; 48 for ( i=0;i<10;i++) 49 { 50 if ((s[i]&x[p][i])>0) break; 51 t[i]=s[i]|x[p][i]; 52 } 53 if (i==10) doit(p+1,t,have+h[p]); 54 if (!yes) doit(p+1,s,have); 55 } 56 int main() 57 { 58 freopen("scifest.in","r",stdin); 59 freopen("scifest.out","w",stdout); 60 while (scanf("%d%d",&n,&m)==2) 61 { 62 work(); 63 yes=0; 64 doit(0,x[19],0);//***p=0 65 if (yes==1) printf("Yes "); 66 else printf("No "); 67 } 68 return 0; 69 }
注意：赋初值。