欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷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;
}
相关标签: DAG最长路