首页 > 代码库 > 拓扑排序

拓扑排序

未经允许,不得转载。

问题 J: 拓扑排序 模板

时间限制: 1 Sec  内存限制: 128 MB

题目描述

一个大工程分成n个子工程,某些子工程之间有相互依赖的关系,比如:b依赖于a,a必须先完成,才能开始完成b,已知完成每个子工程的时间和依赖关系,求n个子工程完成的最小时间。
 
 

 

输入

第一行n(<=100000)和m(<=300000)表示n个子工程,m个依赖关系
第二行n个整数,表示每个子工程所需的时间
接下里m行,每行两个整数a和b,表示b依赖于a

 

输出

工程完成的最小时间

 

样例输入

10 7 801 473 721 201 301 193 991 383 489 945 5 6 2 3 8 10 2 8 10 3 7 4 3 5

样例输出

3016

提示

 
 
如题,luo的拓扑排序
即找最长的一条链。
一:
邻接链保存
二:
dfs遍历(记忆化+每次取最大值)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int read()
{
    int x=0,y=1;
    char ch=getchar();
    while(ch<0||ch>9)
    {
        if(ch==-)
            y=-1;
        ch=getchar();
    }
    while(ch>=0&&ch<=9)
    {
        x=x*10+ch-0;
        ch=getchar();
    }
    return x*y;
}
struct edge
{
    int next,to;
} e[300045];
int pro[100045],cnt,head[100045],f[100045],du[100045];
void add(int from,int to)
{
    e[++cnt].next=head[from];
    e[cnt].to=to;
    head[from]=cnt;
}
int dfs(int x)
{
    if(f[x])
        return f[x];
    int p=head[x],sum=pro[x],maxx=0;
//  printf("x=%d\n",x);
    while(p!=-1)
    {
        f[e[p].to]=dfs(e[p].to);
        if(f[e[p].to]>maxx)
            maxx=f[e[p].to];
        p=e[p].next;
    }
    sum+=maxx;
    return sum;
}
int main()
{
    memset(head,-1,sizeof(head));
    int n=read(),m=read(),x,y,maxn=-2e8;
    for(int i=1; i<=n; i++)
        pro[i]=read();
    for(int i=1; i<=m; i++)
    {
        x=read(),y=read();
        du[y]++;
        add(x,y);
    }
    for(int i=1; i<=n; i++)
    {
        if(du[i])
            continue;
        int l=dfs(i);
//      printf("%d %d\n",i,l);
        if(l>maxn)
            maxn=l;
    }
    cout<<maxn;
    return 0;
}

 

拓扑排序