P2417 课程题解

欧鹰 · 2019-09-05 21:59:25 · 题解

第三篇题解 ，心态有点稳啦。正如就如上一篇题解所说，我欧鹰就是跳下去，也绝对不会给我博客打广告 真香

下面进入这道题的题解

说实话，第一次看到这题。啊！一道蓝题，吓得我加了收藏，就退了出来。做了道紫题，现在闲着无聊就又回来看这题，看了题，又看了数据，这道题真是符合他的标签，水一样颜色的题，简称为水题。

这个题其实就是，从最少人的课程开始遍历，依次递增，在再本课程的人里边选一个人，他可以选的课程最多，并他没有选其他科，就选这个人。

明明标签是图论，但我却写得像贪心，所以欢迎大家HACK！！！！！

下面是代码（代码就不解释啦，不懂得可以私聊，顺便点个赞，谢谢。）

#include<bits/stdc++.h>

using namespace std;

int t,p,n,cnt,vis[100500],head[400500],out[100500],flag;

struct nod{
    int u,v;
}a[100500];

void add(int u,int v)
{
    a[++cnt].u=head[u];

    head[u]=cnt;

    a[cnt].v=v;
}

int read(){
    char ch=getchar(); int f=1,a=0;
    while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); }
    while(isdigit(ch)){ a=a*10+ch-'0';     ch=getchar(); }
    return a*f;
}

struct node{
    int cla,num;
}in[100500];

bool cmp(node a,node b)
{
    return a.num<b.num;
}

int main()
{
    t=read();

    while(t--)
    {
        memset(in,0,sizeof(in));

        memset(out,0,sizeof(out));

        memset(head,0,sizeof(head));

        memset(vis,0,sizeof(vis));

        memset(a,0,sizeof(a));

        cnt=flag=0;

        p=read();

        n=read();

        for(int i=1;i<=p;i++)
        {
            //int num;

            in[i].num=read();

            int numm=in[i].num;

            in[i].cla=i;

            while(numm--)
            {
                int y;

                y=read();

                add(i,y+p);

                out[y+p]++;
            }
        }

        sort(in+1,in+1+p,cmp);

        for(int i=1;i<=p;i++)
        {
            int maxv=21475622,vv=-1;

            for(int j=head[in[i].cla];j;j=a[j].u)
            {
                int v=a[j].v;

                if(out[v]<maxv&&vis[v]!=1)
                {
                    maxv=out[v];

                    vv=v;
                }
            }

            if(vv==-1)
            {
                cout<<"NO"<<'\n';

                flag=1;

                break;
            }

            vis[vv]=1;
        }

        if(flag==0) cout<<"YES"<<'\n';
    }

    return 0;

}