2543 9-6 实现算法greedySetCover
题目描述
集合覆盖问题的一个实例〈X,F〉由一个有限集X及X 的一个子集族F组成。子集族F覆盖了有限集X。也就是说X 中每一元素至少属于F 中的一个子集，即
。对于F中的一个子集C，若C中的X 的子集覆盖了X，即，则称C覆盖了X。集合覆盖问题就是要找出F中覆盖X 的最小子集C*，使得
设计并实现算法greedySetCover，使其计算时间为
实现集合覆盖问题的近似算法greedySetCover。
输入格式:
输入数据第一行有2 个正整数n 和m，分别表示有限集X 中元素个数和子集族 F 中子集个数。X = {0,1,……, n -1}，F= { f1， f2 ，…… fm } 。接下来的 m行中，每行对应于F中一个子集 fi 。第一个数是子集fi 中元素个数ki ，接着的ki 个数表示fi 中的元素。
输出格式:
将计算出的最小覆盖子集输出。第1 行是最小覆盖子集数。第2 行是最小覆盖子集。
输入样例 复制
12 6 6 0 1 2 3 4 5 4 0 3 6 9 4 1 4 7 10 4 4 5 7 8 4 2 5 8 11 2 9 10
输出样例
复制
4 0 4 2 1
