70分求调

P1983 [NOIP2013 普及组] 车站分级

dmx7u19x @ 2023-08-31 13:57:16

#include<bits/stdc++.h>
using namespace std;

int n,m;
vector<int> a[1200];
vector<int> G[1200];
int r[1200];
int v[1200];
bool m1 [1200][1200];

int main()
{
    cin>>n>>m;
    map< pair<int,int> ,bool > mp;
    for(int i=1;i<=m;i++)
    {
        int t=0;
        cin>>t;
        for(int j=0;j<=t-1;j++)
        {
            int p=0;
            cin>>p;
            a[i].push_back(p);
            m1[i][p]=1;
        }
        for(int j=0;j<a[i].size();j++)//停靠枚举站点 
        {
            for(int z=a[i][0];z<a[i][a[i].size()-1];z++)//枚举起始站中间的站点 
            {   
                if(m1[i][z]==1)
                {
                    continue;
                }
                pair<int,int> pr;
                pr.first=a[i][j];
                pr.second=z;
                if(mp.count(pr)==0)
                {
                    G[a[i][j]].push_back(z);
                    r[z]++;
        //cout<<i;                      
                    mp[pr]=1;
                }
                else
                    continue;
            }

        }
    }
    queue< pair<int,int> > q;//表示站点和拓扑轮数 
    for(int i=1;i<=n;i++)
    {
        if(r[i]==0)
        {
            pair<int,int> pr;
            pr.first=i;
            pr.second=1;
            q.push(pr);
            v[i]=1;
        }
    }
    pair<int,int> u;
    int ret=0;
    while(!q.empty())//拓扑排序 
    {
        u=q.front();
        //cout<<u.first<<"  ";
        q.pop();
        for(int i=0;i<G[u.first].size();i++)
        {
            r[G[u.first][i]]--;
            if(r[G[u.first][i]]==0&&v[G[u.first][i]]==0)
            {
                pair<int,int> pr;
                pr.first=G[u.first][i];
                pr.second=u.second+1;
                ret=max(ret,pr.second);
                q.push(pr);
                v[pr.first]=1;
            }
        }
    }
    cout<<ret;
    return 0;
}

by lucky_baizq @ 2023-08-31 14:11:52

你的时间复杂度O(n^3); 定tle了


|