第八个点TLE。实在找不到错了

zhegexiankabutaileng @ 2017-05-13 19:59:44

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
int last[10001]={0},t[5005]={0},oc[5005]={0},in[5005]={0};
int que[5005]={0},tque[5005]={0};
int n=0,m=0,ne=0,vir=1005,ans=0,lim=0;
struct edge{
    int from,to,pre;
}e[1000001];
void add(int x,int y)
{
    ne++;
    e[ne].from=x;
    e[ne].to=y;
    e[ne].pre=last[x];
    last[x]=ne;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int q=0;
        //cin>>q;
        scanf("%d",&q);
        vir++;
        memset(oc,0,sizeof(oc));
        for(int j=1;j<=q;j++)
        {
            int qq=0;
            //cin>>qq;
            scanf("%d",&qq);
            t[j]=qq;
            oc[qq]=1;
            add(qq,vir);
        }
        for(int j=t[1];j<=t[q];j++)
        {
            if(oc[j]==0)
            {
                add(vir,j);
                in[j]+=q;
            }
        }
    }
    for(int i=1;i<=n;i++) if(in[i]==0) que[++lim]=i;
    int x=0;
    while(lim!=0)
    {
        int tlim;
        for(tlim=1;tlim<=lim;tlim++) tque[tlim]=que[tlim];
        lim=0;
        ans++;
        for(int iii=1;iii<=tlim;iii++)
        {
            int i=tque[iii];
            if(in[i]==0)
            {
                x++;
                in[i]=-2;
                for(int k=last[i];k!=0;k=e[k].pre)
                {
                    int ii=e[k].to;
                    for(int kk=last[ii];kk!=0;kk=e[kk].pre)
                    {
                        if(in[e[kk].to]>0) in[e[kk].to]--;
                        if(in[e[kk].to]==0)
                        {
                            que[++lim]=e[kk].to;
                        } //in[e[kk].to]=-1;
                    }
                }
            }
        }
        //for(int i=1;i<=n;i++) if(in[i]==-1) in[i]=0;
    }
    cout<<ans;
}

by 该用户已注册 @ 2017-05-18 22:27:24

用scanf就过了

by foreverpiano @ 2017-05-24 18:34:19

@ zhegexiankabutaileng 三重循环感觉有点多，不加优化会炸，我是用队列来储存的，你可以参考一下

#include<bits/stdc++.h>
#define maxn 1100
using namespace std;
int book[maxn][maxn],du[maxn];
int n,m,x,y;
int ans=0;
int s[maxn];
int judge[maxn];
void topusort()
{
    int num=0;
    queue<int > q;    
    while(num<n)
    {        
        for(int i=1;i<=n;i++)
          if(du[i]==0)
          {
              du[i]=-1;     
              q.push(i);
              num++; 
          }
          ans++;
          while(!q.empty())
          {
             int k=q.front();q.pop();
             for(int j=1;j<=n;j++)
                    if(book[k][j]==1)
                    {
                       book[k][j]=0;
                       du[j]--;
                   }
          }           
      }
}
void init()
{
   cin>>n>>m;
   while(m--)
   {
         int x;
         memset(judge,0,sizeof(judge));
         cin>>x;
         for(int i=1;i<=x;i++)
         {
            cin>>s[i];
            judge[s[i]]++;
        }
        for(int i=s[1];i<=s[x];i++)
           if(!judge[i])
           {
               for(int j=1;j<=x;j++)
                 book[i][s[j]]=1;        
             }
   }
   for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
       if(book[i][j])              
           du[j]++;
}
void output()
{
    cout<<ans<<endl;
}
int main()
{
         ios::sync_with_stdio(false);
      init();
      topusort();
      output();
    return 0;
}

by ezoiHQM @ 2017-08-09 15:51:48

输入输出优化：

inline int read() {
    int x = 0 , f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

by pengpeng2002 @ 2017-08-12 13:39:47

别重复加边，我一开始重复加边，后来加了个 if 这条边没有 then 加边 就好了

by bymlg001 @ 2017-09-17 21:50:44

你重复加边竟然只有一个点没过，我用读入优化还有三个点没过。用个二维数组去重就好了。

by zzq233 @ 2018-07-25 12:05:28

重复加边八 九点MLE