Le Petit Prince

指纹覆盖

 Published On August 04, 2015

描述

少写点正则一直是每个实习生的梦想。（懒～

周一Loading又发任务包了，给了一大堆的指纹，啥设备都有：Nginx，Cisco SSH，VoIP，Apache httpd，Apache Tomcat
，Apache Traffic Server，Apache Traffic Server 5.3.1，Apache Traffic Server 5.3.10086 等等……

实习生们又头大了，这得写多少指纹啊？ Peter是个很懒的实习生，他正在琢磨一种方法尽可能地少写指纹：已知指纹的全集 U={0,2,3…n-1}，能用作匹配的正则集合 F={S1,S2…Sm} 每条正则Sk能覆盖的指纹 Sk为 U 的一个子集。Peter想找出一种方案，用最少数量的正则去覆盖整个指纹全集 U 。看起来很难的样子，Peter感觉自己智商捉急，任务期限又特别紧，你能帮帮他吗？

比如:

  • U = {0,1,2,3,4,5,6,7,8,9,10,11}
  • F = {S0,S1, S2, S3, S4, S5}
  • S0 = {0,1,2,3,4,5}, S1 = {4,5,7,8} , S2 = {0,3,6,9} ,　S3 = {1,4,6,7,10} , S4 = {2,5,8,11}, S5 = {9,10}。
  • 其最小的集合覆盖C={S2, S3, S4}

输入要求

第一行有2个正整数n和m，(1 <= n <= 6000 , 1 <= m <= 600)分别表示有限集X中元素个数和子集族F中子集个数。X = {0,1,.., n -1}, F = {S1,S2 , … ,Sm-1}。 　　接下来的m行中，每行对应F中一个子集Si。第一个数是子集Si中元素个数ki，接着的ki个数表示Si中的元素。

输出要求

输出第一行表示最小的覆盖数C*,(设最优解为C，C*在范围[C , 1.84×C]内即可)。我们的输入保证存在解。

第二行有C*个整数，表示最小的覆盖子集序号 S1,S2…(子集可以任意序列输出，但不能有重复的数，两个数间用空格隔开)。

输入样例

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

评测系统链接

代码

#include <cstdio>
#include <cstdlib>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
int n,m;
int set_array[10000];
int V[605][100];
int C[10000];
int ans[1000],anss;
int vis[1000],current;
void read()
{
    scanf("%d",&n);
    scanf("%d",&m);
    for(int i=0;i<m;i++)
    {
        int n1;
        scanf("%d",&n1);
        for(int j=0;j<n1;j++)
        {
            scanf("%d",&set_array[j]);
        }
        sort(set_array,set_array+n1);
        V[i][0]=n1;
        for(int j=1;j<=n1;j++)// 1~n1
        {
            V[i][j]=set_array[j-1];
        }
    }
}

void update(int vit,int mit)
{
	int diff=0,vi=0,mi=0;
	while(vi<V[vit][0]&&mi<V[mit][0])
	{
		if(V[vit][vi+1]<V[mit][mi+1])
		{
			set_array[diff++]=V[vit][vi+1];
			vi++;
		}
		else if(V[vit][vi+1]>V[mit][mi+1])
		{
			mi++;
		}
		else{
			vi++;
			mi++;
		}
	}
	while(vi<V[vit][0])
	{
		set_array[diff++]=V[vit][vi+1];
		vi++;
	}
	if(diff==0)
	{
    	current++;
		vis[vit]=1;
		return;
	}
	V[vit][0]=diff;
	for(int i=0;i<diff;i++)
	{
		V[vit][i+1]=set_array[i];
	}
}

int selectNew()
{
    int res=0;
    int max_score=0;
    for(int vit = 0;vit < m;vit++)
    {
        if(vis[vit])continue;
        int score = V[vit][0];
        if(score>max_score)
        {
            max_score=score;
            res=vit;
        }
    }
    // printf("res= %d\n",res);
    // merge(res);
    vis[res]=1;
    current++;
    return res;
}
 
void solve()
{
    current=0;
    while(current < m)
    {
        int it = selectNew();
        ans[++anss]=it;
        for(int i=0;i<m;i++)
        {
        	if(vis[i])continue;
        	update(i,it);
        }
    }
    // printf("%d %d\n",current,n);
    printf("%d\n",anss);
    for(int i=1;i<=anss;i++)
    {
        printf("%d ",ans[i]);
    }
}
int main()
{
    read();
    solve();
}

Tags: Algorithm

← Previous
Next →

Comments: