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
下面是对标程中的一些难理解的代码的解释：
int x[][],h[];
x[20][10]:最大二进制数31位，此处有300个学生，把每一项活动的300个用10组二进制数记录其 1 的位置。
if (a==)
{
x[i][j/]+=<<(j%);
h[i]++;
}
1、x[i][j/31]：第 i 个项目 第 k 组 ，如果参加。一个二进制数为32位，一位符号位，/31 即这个1 在第几组 上,j %31 即这一组的第几位上是 1。
for ( i=;i<;i++)
{
if ((s[i]&x[p][i])>) break;
t[i]=s[i]|x[p][i];
}
这里是选择活动时的操作：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可以选]）
另外，还要按照活动的参与人数进行排序，人多的先选。
下面是完整代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int n,m;
int x[][],h[];
bool yes=;
void work()
{
memset(x,,sizeof (x));
for (int i=;i<n;i++)
{
h[i]=;
for (int j=;j<m;j++)
{
int a;
scanf("%d",&a);
if (a==)
{
x[i][j/]+=<<(j%);
h[i]++;
}
}
}
int k;
for (int i=;i<n-;i++) //? n-1
for (int j=i+;j<n;j++)
{
if (h[i]<h[j])
{
k=h[i];h[i]=h[j];h[j]=k;
for (int t=;t<;t++)
{
int u=x[i][t];x[i][t]=x[j][t];x[j][t]=u;
}
}
}
}
void doit(int p,int s[],int have)
{
if (p==n)
{
if (have==m) yes=;
return ;
}
int t[],i;
for ( i=;i<;i++)
{
if ((s[i]&x[p][i])>) break;
t[i]=s[i]|x[p][i];
}
if (i==) doit(p+,t,have+h[p]);
if (!yes) doit(p+,s,have);
}
int main()
{
freopen("scifest.in","r",stdin);
freopen("scifest.out","w",stdout);
while (scanf("%d%d",&n,&m)==)
{
work();
yes=;
doit(,x[],);//***p=0
if (yes==) printf("Yes\n");
else printf("No\n");
}
return ;
}
注意：赋初值。