算法学习之路|有向无环图(DAG)求最长路

原题为2017暑假acm亚洲区预赛乌鲁木齐赛区的H题,看紫书时看到DAG就把这题找了出来,毕竟也是少数自己参加过的比赛。

本题题意:在有n个站点,m条从高到低的滑雪路径的滑雪场上,找出一条加起来滑的最远的路径(只能从高到低划)。转化一下就是,给一张有向无环图(无负权边),求最长路。

因为是水题,没有卡空间或时间,也不需要考虑数据溢出,还算良心=_=

ac代码:(敲了好久啊——真是菜)

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int u[100005],v[100005];
int w[100005],d[10005],r[10005];
int first[10005],next1[100005];
int n,m;
int dp(int i)//i表示第i个点
{
    if(d[i]>0)
        return d[i];
    int k=first[i];//k表示第k条边
    while(k!=-1)
    {
        d[i]=max(d[i],dp(v[k])+w[k]);
        k=next1[k];
    }
    return d[i];
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int ans=0;
        memset(first,-1,sizeof(first));
        memset(d,0,sizeof(d));
        memset(r,0,sizeof(r));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u[i],&v[i],&w[i]);
            next1[i]=first[u[i]];
            first[u[i]]=i;//邻接表存储
            r[v[i]]++;//入度
        }
        for(int i=1;i<=n;i++)
        {
            if(r[i]==0)
                ans=max(ans,dp(i));
        }
        printf("%d\n",ans);
    }
    return 0;
}

写这道题顺便回顾了一下邻接表,不过用数组表示的邻接表看起来可能没有指针表示或者用stl来的直观。

好久不敲代码,初始化都没注意,卡了好久才发现。

顺便记一下邻接表

u,v,w三个数组分别保存边的起始点,指向点和边的权值。

first数组存储每一点的其中一条从此点出发的边的编号,例如:first[2]=5表示编号为2的点的其中一条边的编号为5.

next数组存储以某一点为出发点的一条边的下一条边的编号,例如:next[5]=3表示编号为5的边的出发点(比如说点1)的下一条边的编号是3。这样就可以通过forst和next数组遍历每一个点的每一条边了,且对于稀疏图而言,占内存远小于邻接矩阵。

许多简单的dp问题可以转化为DAG问题。紫书上的例子:选择不同面值的硬币到达指定面额,可以转化成求一条从面额s到0的满足题意的路径,因为硬币面额不可能是负的或0,所以这也是一个DAG问题。

上一篇:"Navicat导入数据报错 1153-Gotapacketbiggerthan'maxallowedpacket'bytes"


下一篇:在Object-C中学习排序算法