[CF1105E] Helping Hiaset

问题描述

你在某社交网站上面注册了一个新账号，这个账号有\(n(n\leq 10^5)\)次记录。要么就是你更改过一次ID，要么就是一个ID为\(s(|s|\leq 40)\)的朋友访问过你的空间。

你有\(m(m\leq 40)\)个朋友。每一个朋友都会访问你的空间至少一次。如果这一个朋友每一次访问你的空间的时候，你的ID和它的ID一样，那么他就会高兴。 求你最多能让多少人高兴。

输入格式

第一行一个两个正整数n,m. 接下来n行每行表示一次记录，有如下两种格式：

1

2 s

其中1表示你更改过一次ID，2表示你的一个ID为s的朋友访问过一次你的空间。

保证第一个记录一定是1。

输出格式

一行，一个正整数，表示最多能让多少个朋友高兴。

样例输入

5 3
1
2 motarack
2 mike
1
2 light

样例输出

2

解析

如果把每个人出现的时间段记录下来，就得到了每一个人的出现的时间段的集合。而如果两个人的集合的交集是空集，那么这两个人就可以同时高兴。这样，问题就转化为了求最多的人使这些人出现时间的集合交集为空。把交集不为空的两个人连边，这就变成了一个图上最大独立集的问题。

具体关于交集的判断，可以用bitset对每个人维护一个二进制数，如果两个人的二进制数的与不为0，就说明有交集。

代码

#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
#include <bitset>
#include <algorithm>
#define N 100002
#define M 42
using namespace std;
int head[M],ver[M*M],nxt[M*M],l;
int n,m,i,j,cnt1,cnt2,ans,p[M];
bool vis[M];
map<string,int> d;
bitset<N> b[M];
void insert(int x,int y)
{
    l++;
    ver[l]=y;
    nxt[l]=head[x];
    head[x]=l;
}
int main()
{
    cin>>n>>m;
    for(i=1;i<=m;i++) p[i]=i;
    for(i=1;i<=n;i++){
        int op;
        string s;
        cin>>op;
        if(op==1) cnt1++;
        else{
            cin>>s;
            if(d[s]==0) d[s]=++cnt2;
            b[d[s]][cnt1]=1;
        }
    }
    for(i=1;i<=m;i++){
        for(j=i+1;j<=m;j++){
            if((b[i]&b[j]).any()) insert(i,j),insert(j,i);
        }
    }
    int t=100;
    while(t--){
        random_shuffle(p+1,p+m+1);
        int tmp=0;
        memset(vis,0,sizeof(vis));
        for(i=1;i<=m;i++){
            if(!vis[p[i]]){
                tmp++;
                for(j=head[p[i]];j;j=nxt[j]) vis[ver[j]]=1;
            }
        }
        ans=max(ans,tmp);
    }
    printf("%d\n",ans);
    return 0;
}

[CF1105E] Helping Hiaset

原文：https://www.cnblogs.com/LSlzf/p/11878210.html