洛谷 P3068 【[USACO13JAN]派对邀请函Party Invitations】题解

因为直接按照存每组的奶牛会存在 浪费 的情况，会超内存，因此这里采用线性存储的方法，将 所有奶牛存在一个数组 中，然后每个组保存一个头和尾标记来表明这个组的奶牛在数组中的什么位置。然后就是一个大暴力，一直计算邀请了当前奶牛后还需要邀请哪些奶牛，直到没有奶牛需要邀请。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int kid[1000001],size[250001],zu[250002][3],invite[1000001],use[250001],pa[250001];//kid表示奶牛，size记录每组的大小，zu记录每组的头和尾标记，invite记录此奶牛是否邀请过，use记录此组是否邀请过，
int main()
{
    int n,g,sum=0,ans,daan=100000000;
    cin>>n>>g; 
    for(int i=1;i<=g;i++)
    {
        cin>>size[i];
        for(int j=1;j<=size[i];j++)
            cin>>kid[++sum];
        zu[i][1]=zu[i-1][2]+1;
        zu[i][2]=zu[i-1][2]+size[i];//记录头尾标记
    } 
    ans=0; 
    invite[1]=1;//初始化（奶牛1首先被邀请）
    int pan;
    do
    {
        pan=0;
        for(int k=1;k<=g;k++)
        {
            if(use[k]==0)//如果这个组还没有被邀请就检查现在是否需要邀请
            {
                int len=0;
                for(int j=zu[k][1];j<=zu[k][2];j++)
                    if(invite[kid[j]]==1)
                        len++;//寻找当前组已经有多少头牛被邀请
                if(len==size[k]-1)//如果被邀请的奶牛数为当前奶牛数-1就邀请当前组
                {
                    use[k]=1;
                    pan=1;
                    for(int j=zu[k][1];j<=zu[k][2];j++)
                        invite[kid[j]]=1;
                }
                if(len==size[k])
                    use[k]=1;//排除一个组的奶牛已经全部被邀请却没有被标记的，节省时间
            }
        }
    }while(pan==1);//只有有新的奶牛被邀请时才需要再此寻找新的组
    for(int i=1;i<=n;i++)//找哪些奶牛被邀请了
    if(invite[i]==1)
      ans++;
    cout<<ans;
    return 0;
}