洛谷1983(DAG上最长路)
程序员文章站
2024-02-24 17:38:37
...
传送门
停车点连向不停车点,重复的边只连一次,最后求一个DAG(有向无环图)上最长路即可。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int maxn=1002;
int n,m;
int head[maxn],edge;
struct EDGE {
int v,nxt;
}e[maxn*maxn];
int vis[maxn][maxn],t[maxn];
inline int read() {
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
inline void adde(int u,int v) {
e[edge].v=v,e[edge].nxt=head[u],head[u]=edge++;
}
int f[maxn];
int dfs(int p) {
for (int i=head[p];~i;i=e[i].nxt) {
int v=e[i].v;
f[p]=max(f[p],f[v]?f[v]:f[v]=dfs(v));
}
return ++f[p];
}
int main() {
// freopen("P1983.in","r",stdin);
while (~scanf("%d%d",&n,&m)) {
memset(t,0,sizeof(t));
memset(vis,0,sizeof(vis));
memset(f,0,sizeof(f));
memset(head,-1,sizeof(head)),edge=0;
while (m--) {
int num=read();
for (int i=1;i<=num;++i) t[i]=read();
int s=1;
for (int i=t[1];i<t[num];++i)
if (t[s]==i) ++s;
else
for (int j=1;j<=num;++j)
if (!vis[t[j]][i])
vis[t[j]][i]=1,adde(t[j],i);
}
int res=0;
for (int i=1;i<=n;++i)
if (!f[i]) res=max(res,f[i]=dfs(i));
printf("%d\n",res);
}
return 0;
}
推荐阅读