(一周没写过随笔了）
这道题有坑！
看到题目，发现这么明显（？？）的要求顺序，还有什么想法，拓扑！
将每条路范围内等级大于等于它的点（不能重复（坑点1））和它连一条边，注意起点终点都要有（坑点2），然后拓扑求解即可。
BFS的拓扑感觉更好。
然后打了个map判重交上去帅气的TLE了3个点
#include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<map> using namespace std; const int N=1005; vector <int> a[N]; map <int,bool> ma[N]; int n,i,m,j,q[N*2+10],head,tail,s[N],x,k,ru[N],bs[N],ans; bool f[N]; inline void read(int &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } int main() { read(n); read(m); for (i=1;i<=m;++i) { memset(f,0,sizeof(f)); read(s[0]); for (j=1;j<=s[0];++j) read(s[j]),f[s[j]]=1; for (j=s[1]+1;j<=s[s[0]];++j) if (!f[j]) for (k=1;k<=s[0];++k) if (!ma[s[k]][j]) a[s[k]].push_back(j),ru[j]++,ma[s[k]][j]=1; } for (i=1;i<=n;++i) if (!ru[i]) q[++tail]=i,bs[i]=1; while (head<tail) { int now=q[++head]; for (i=0;i<a[now].size();++i) { int k=a[now][i]; bs[k]=bs[now]+1; ans=max(ans,bs[k]); if (!(--ru[k])) q[++tail]=k; } } printf("%d",ans); return 0; }
然后一想，N<=1000至于用map么。然后直接二维数组判断，然后过了。。。
#include<cstdio> #include<vector> #include<cstring> #include<iostream> using namespace std; const int N=1005; vector <int> a[N]; int n,i,m,j,q[N*2+10],head,tail,s[N],x,k,ru[N],bs[N],ans; bool f[N],p[N][N]; inline void read(int &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } int main() { read(n); read(m); for (i=1;i<=m;++i) { memset(f,0,sizeof(f)); read(s[0]); for (j=1;j<=s[0];++j) read(s[j]),f[s[j]]=1; for (j=s[1];j<=s[s[0]];++j) if (!f[j]) for (k=1;k<=s[0];++k) if (!p[s[k]][j]) a[s[k]].push_back(j),ru[j]++,p[s[k]][j]=1; } for (i=1;i<=n;++i) if (!ru[i]) q[++tail]=i,bs[i]=1; while (head<tail) { int now=q[++head]; for (i=0;i<a[now].size();++i) { int k=a[now][i]; bs[k]=bs[now]+1; ans=max(ans,bs[k]); if (!(--ru[k])) q[++tail]=k; } } printf("%d",ans); return 0; }
一道坑题！