频道栏目
首页 > 考试 > 其他 > 正文
The Cow Doctor【bitset+枚举】
2018-05-05 10:25:37      个评论    来源:海岛Blog  
收藏   我要投稿

The Cow Doctor【bitset+枚举】。

Texas is the state having the largest number of cows in the US: according to the 2005 report of the NationalAgricultural Statistics Service, the bovine population of Texas is 13.8 million. This is higher than thepopulation of the two runner-up states combined: there are only 6.65 million cows in Kansas and 6.35millions cows in Nebraska.?

There are several diseases that can threaten a herd of cows, the most feared being ``Mad Cow Disease" or Bovine Spongiform Encephalopathy (BSE); therefore, it is very important to be able to diagnose certain illnesses. Fortunately, there are many tests available that can be used to detect these diseases.?

A test is performed as follows. First a blood sample is taken from the cow, then the sample is mixed with a test material. Each test material detects a certain number of diseases. If the test material is mixed with a blood sample having any of these diseases, then a reaction takes place that is easy to observe. However, if a test material can detect several diseases, then we have no way to decide which of these diseases is present in the blood sample as all of them produce the same reaction. There are materials that detect many diseases (such tests can be used to rule out several diseases at once) and there are tests thatdetect only a few diseases (they can be used to make an accurate diagnosis of the problem).?

The test materials can be mixed to create new tests. If we have a test material that detects diseases A and B; and there is another test material that detects diseases B and C, then they can be mixed toobtain a test that detects diseases A, B, and C. This means that if we have these two test materials, then there is no need for a test material that tests diseases A, B, and C-such a material can be obtained bymixing these two.?

Producing, distributing, and storing many different types of test materials is very expensive, and inmost cases, unnecessary. Your task is to eliminate as many unnecessary test materials as possible. Ithas to be done in such a way that if a test material is eliminated, then it should be possible to mix an equivalent test from the remaining materials. (``Equivalent" means that the mix tests exactly the samediseases as the eliminated material, not more, not less).

Input

The input contains several blocks of test cases. Each case begins with a line containing two integers: the number 1 ≤ n ≤ 300 of diseases, and the number 1 ≤ m ≤ 200 of test materials. The next m lines correspond to the m test materials. Each line begins with an integer, the number 1 ≤ k ≤ 300 of diseases that the material can detect. This is followed by k integers describing the k diseases. These integers are between 1 and n .?

The input is terminated by a block with n = m = 0 .

Output

For each test case, you have to output a line containing a single integer: the maximum number of test materials that can be eliminated.

Sample Input

10 5
2 1 2
2 2 3
3 1 2 3
4 1 2 3 4
1 4
3 7
1 1
1 2 
1 3
2 1 2
2 1 3
2 3 2
3 1 2 3
0 0

Sample Output

2
4

Hint

Huge input file, 'scanf' recommended to avoid TLE.?

Source

Central Europe 2005

Regionals 2005?>>?Europe - Central

问题分析:

 一个集合,问该集合是否为其它一些集合的并集。

 先占个位置不解释。

AC的C++语言程序如下:

/* POJ2943 UVALive3524 The Cow Doctor */

#include 
#include 
#include 

using namespace std;

int const N = 300;
bitset a[N + 1], b[N + 1];

int main()
{
    ios::sync_with_stdio(false);

    int n, m, k, v;
    while(cin >> n >> m && (n || m)) {
        for(int i = 0; i < m; i++)
            a[i] = 0, b[i] = 0;

        for(int i = 0; i < m; i++) {
            cin >> k;
            while(k--) {
                cin >> v;
                a[i].set(v);
            }

            for(int j = 0; j < i; j++)
                if((a[i] & a[j]) == a[i])
                    b[j] |= a[i];
                else if((a[i] & a[j]) == a[j])
                    b[i] |= a[j];
        }

        int cnt = 0;
        for(int i = 0; i < m; i++)
            if(a[i] == b[i])
                cnt++;
        cout << cnt << endl;
    }

    return 0;
}

点击复制链接 与好友分享!回本站首页
上一篇:编程开发瞬间移动问题解析
下一篇:利用collections类中的defaultdict函数,生成一个my_list字典
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站