【问题描述】
一年一度的科技节即将到来。同学们报名各项活动的名单交到了方克顺校长那，结果校长一看皱了眉头：这帮学生热情竟然如此高涨，每个人都报那么多活动，还要不要认真学习了？！这样不行！……于是，校长要求减少一些活动，使每位学生只能参加一项（一名同学要参加某活动，必须已报名且该活动未被去掉）。当然，他也不希望哪位同学因此不能参加任何活动。他想知道自己的方案能否实行。
【输入】
输入文件名为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。
这题开始以为是用动态规划，后来发现n这么小应该使用搜索，后来经老师介绍，如果纯搜索+数组的话只能过6组数据，而加上二进制就可以全过
boolean数组其实既浪费内存又浪费时间，1个字节8个二进制位，而事实上储存true和false只用1个二进制位，所以用unsigned int类型的32个二进制位
来存储这些true和false的数据。其它都比较简单，直接就发代码了
Code
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
using namespace std;
#define k 32
typedef bool boolean;
ifstream fin("scifest.in");
ofstream fout("scifest.out");
boolean found;
int m,n;
int buf;
typedef struct myData{
int peo;
unsigned int activities[];
}myData;
myData *s;
unsigned int ac[];
boolean cmp(const myData& a,const myData& b){
return a.peo > b.peo;
}
boolean init(){
if(!(fin>>n>>m)) return false;
s = new myData[(const int)(n + )];
found = false;
for(int i = ;i < n;i++){
s[i].peo = ;
memset(s[i].activities, , sizeof(s[i].activities));
for(int j = ;j < m;j++){
fin>>buf;
if( buf == ){
s[i].peo++;
s[i].activities[j/k] += << (j % k);
}
}
}
sort(s,s + n,cmp);
return true;
}
void free_MyPointer(){
delete[] s;
}
void find(int vi,unsigned int *sed,int join){
if(vi == n){
if(join == m) found = true;
return ;
}
unsigned int t[];
boolean aFlag = true;
for(int i = ;i <= m/k;i++){
if((sed[i] & s[vi].activities[i]) != ){
aFlag = false;
break;
}
t[i] = sed[i] | s[vi].activities[i];
}
if(aFlag) find(vi + , t, join + s[vi].peo);
if(!found) find(vi + , sed, join);
}
int main(){
while(init()){
find(, ac, );
if(found) fout<<"Yes"<<endl;
else fout<<"No"<<endl;
free_MyPointer();
}
return ;
}