为什么第七个点TLE……求指出!

P1983 [NOIP2013 普及组] 车站分级

凋零傲风 @ 2016-11-18 21:33:50

很奇怪!为什么第七个点不过……关键数据还下载不下来,说是太大了,太大了?

// SS[0]中的车站,被认为都是级别1
// SS[1]-SS[0]的车站,被认为都是级别2
// SS[2]-SS[0]-SS[1]的车站,被认为都是级别3
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int Input(vector<vector<int> > &SS);
void InitGraph(vector<vector<int> > &SS, vector<vector<int> >& M);
void Remove(vector<int> &a, vector<int> &b);
int Search(vector<int> &a,int x);
void Print(vector<vector<int> > &SS);
void TopoSort(vector<vector<int> >& G);

int main()
{
    // 读文件
    vector<vector<int> > SS; 
    int n=Input(SS);
    // 构造有向图的邻接矩阵
    vector<vector<int> > G(n,vector<int>(n)); 
    InitGraph(SS, G);
    // 分级别拓扑排序
    TopoSort(G);
    return 0;
}

void TopoSort(vector<vector<int> >& G)
{
    int n=G.size();
    // 计算入度表
    vector<int> inDegree(n,0);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(G[i][j]==1)
                inDegree[j]++;
    // 入度为0的进队列
    queue<pair<int,int> > Q;  // <站的下标 站的级别 >
    for(int i=0; i<n; i++)
        if(inDegree[i]==0)
            Q.push( pair<int,int> (i,1) );
    pair<int,int> v;
    while( !Q.empty() )
    {
        v=Q.front(); Q.pop();
        for(int i=0; i<n; i++)
        {
            if(G[v.first][i]==1)
            {
                inDegree[i]--;
                if(inDegree[i]==0) 
                    Q.push( pair<int,int> (i,v.second+1)  );
            }
        }
    }
    cout<<v.second<<endl;
}

void InitGraph(vector<vector<int> > &SS, vector<vector<int> >& G)
{
    for(int i=0; i<SS.size(); i++)
    {
        int s=SS[i][0], e=SS[i][SS[i].size()-1]; // 起点站、终点站
        vector<int> nostop;
        for(int k=s; k<=e; k++)  nostop.push_back(k);
        Remove(nostop, SS[i]);
        for(int i1=0; i1<nostop.size(); i1++)
            for(int j1=0; j1<SS[i].size(); j1++)
            {
                int ii=nostop[i1], jj=SS[i][j1];
                G[ii][jj]=1;
            }
    }
}

// a-b存入a
void Remove(vector<int> &a, vector<int> &b)
{
    for(int i=0; i<b.size(); i++)
    {
        int k=Search(a,b[i]);
        if(k!=-1)
            a.erase(a.begin()+k); 
    }
}

int Search(vector<int> &a,int x)
{
    for(int i=0; i<a.size(); i++)
        if(a[i]==x)
            return i;
    return -1;
}

int Input(vector<vector<int> > &SS)
{
    int n;    cin>>n;  // 车站数
    int m;    cin>>m;  // 车次数
    for(int i=0; i<m; i++)
    {
        int k; cin>>k;    // 每次车的停站数
        vector<int> Si;   // 每次车的停站向量
        for(int j=0; j<k; j++)
        {
            int id; cin>>id;  id--;
            Si.push_back(id);
        }
        SS.push_back(Si);
    }
    return n;
}

by KEIONG @ 2017-08-17 09:24:09

我第七和第八TLE orz


|