tie是什么
by Monkey_Hunter @ 2020-02-15 15:46:51
自觉没啥问题,就是每次把入度为0的点放入,然后找其能到哪些点,然后减入度,再放入。
按理一个点最多放入队列一次,每条边也最多算一次复杂度不应该是N+M吗?
by 190040257a @ 2020-02-15 15:47:45
@[190040257a](/user/233957)
把数组开大点
有的时候会蜜汁TLE
by michael_song @ 2020-02-15 18:13:14
@[michael_song](/user/193158) 貌似没啥效果,时间超了0.2s
by 190040257a @ 2020-02-15 18:41:03
@[190040257a](/user/233957)
这是我的代码
你重点看一下50多行
```
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int M=1010;
int n,m;
int head[M],indeg[M],result;
bool ki[M];
int a[M][M],ans[M],as[M];
queue <int> Q;
int maxn(int a,int b)
{
if(a>b)
return a;
else
return b;
}
void tps()
{
for(int i=1;i<=n;i++)
if(!indeg[i])
{
Q.push(i);
ans[i]=1;
}
while(!Q.empty())
{
int s=Q.front();
Q.pop();
for(int i=1;i<=n;i++)
{
if(a[s][i])
{
indeg[i]--;
ans[i]=maxn(ans[s]+1,ans[i]);
if(!indeg[i])
Q.push(i);
}
}
}
}
int main()
{
int i,j,k,si;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
memset(ki,false,sizeof(ki));
memset(as,0,sizeof(as));
scanf("%d",&si);
for(j=1;j<=si;j++)
{
scanf("%d",&as[j]);
ki[as[j]]=true;
}
for(j=as[1]+1;j<=as[si];j++)
if(!ki[j])
for(k=1;k<=si;k++)
if(!a[j][as[k]])
{
a[j][as[k]]=1;
indeg[as[k]]++;
}
}
tps();
for(i=1;i<=n;i++)
result=maxn(result,ans[i]);
printf("%d",result);
return 0;
}
```
by michael_song @ 2020-02-15 18:48:28
@[michael_song](/user/193158) 感觉我的代码跟你的思路差不多呀
by 190040257a @ 2020-02-16 15:56:30
@[自动WA机私信我](/user/249786) 领带
by jijidawang @ 2020-02-21 16:17:38