题解 P1983 【车站分级】

_•́へ•́╬_ · 2018-10-01 09:31:59 · 题解

暴力大法好

下面给出我各个变量的解释

• a[i]\text{表示第}i\text{个车站的分级}
• s[i]\text{表示第i}\text{趟车次经过的站数}
• f[i][j]\text{表示第}i\text{趟车次停靠的第}j\text{个车站}
• have[i][j]\text{表示第}i\text{趟车次是否经过第}j\text{个车站}

#include<bits/stdc++.h>//懒人专用头文件
#define max(x,y) ((x)>(y)?(x):(y))
#define rpt(n) for(register int ttxyc=0;ttxyc<(n);++ttxyc)//宏定义
using namespace std;
inline int read()//快读
{
    register int x=0,t=0;register char c=getchar();for(;c<'0'||c>'9';t|=c=='-',c=getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=getchar());return t?-x:x;
}
int n,m,a[1000],f[1000][1000],s[1000];bool have[1000][1000];
main()
{
    n=read();m=read();
    rpt(n)a[ttxyc]=1;
    rpt(m)
    {
        s[ttxyc]=read();
        for(register int i=0;i<s[ttxyc];++i)f[ttxyc][i]=read()-1,have[ttxyc][f[ttxyc][i]]=1;
    }
    //以上均为输入
    for(;;)//屎循环
    {
        bool cd=0;//是否更改
        rpt(m)
        {
            int maxn=0;
            for(register int i=f[ttxyc][0];i<=f[ttxyc][s[ttxyc]-1];++i)
                if(!have[ttxyc][i])maxn=max(maxn,a[i]);//不停靠的取最大值
            ++maxn;//停靠的比不停靠的至少多一
            for(register int i=0;i<s[ttxyc];++i)
                if(a[f[ttxyc][i]]<maxn)a[f[ttxyc][i]]=maxn,cd=1;//有的分级不符合要求，更改
        }
        if(!cd)break;//没更新的就说明已经是最优解
    }
    int maxn=0;
    rpt(n)maxn=max(maxn,a[ttxyc]);
    printf("%d",maxn);
}