70分求助!

P1983 [NOIP2013 普及组] 车站分级

AC_NOIP_AK_IOI @ 2023-02-05 16:07:47

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,f[1001],in[1001],b[1001],maxn;
bool flag[1001];
vector<int> adj[1001];
queue<int> q;
void bfs()
{
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        for(int i=0;i<adj[t].size();i++)
        {
            int x=adj[t][i];
            f[x]=max(f[x],f[t]+1);
            in[x]--;
            if(in[x]==0)q.push(x);
        }
    }
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x;
        cin>>x;
        memset(flag,0,sizeof(flag));
        for(int j=1;j<=x;j++)
        {
            cin>>b[j];
            flag[b[j]]=1;
        }
        for(int j=b[1];j<=b[x];j++)
        {
            if(!flag[j])
            {
                for(int k=1;k<=x;k++)
                {
                    if(!count(adj[j].begin(),adj[j].end(),b[k])) //这个指令是看adj[j]数组里有没有b[k]这个元素
                    {
                        adj[j].push_back(b[k]);
                        in[b[k]]++;
                    }
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(in[i]==0)f[i]=1,q.push(i);
    }
    bfs();
    for(int i=1;i<=n;i++)maxn=max(maxn,f[i]);
    cout<<maxn;
    return 0;
}

最后三个点TLE。QAQ


by YJM_yejiaming @ 2023-02-05 16:13:04

dfs中TLE百分之八九十是没记忆化搜索


by AC_NOIP_AK_IOI @ 2023-02-05 16:38:40

@YJM_yejiaming,我是bfs。


by AC_NOIP_AK_IOI @ 2023-02-09 20:38:27

此题已AC!此贴终结!


|