洛谷 P1807 最长路_NOI导刊2010提高（07）题解

相当与一个拓扑排序的模板题吧

蒟蒻的辛酸史

题目大意：给你一个有向无环图，让你求出1到n的最长路，如果没有路径，就输出-1

思路：一开始以为是一个很裸的拓扑排序

就不看题目，直接打了一遍拓扑排序

然后就得到了45分的成绩

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<cmath>

#define int long long int 

using namespace std;

struct node

{

    int u;

    int v;

    int w;

    int next;

}data[];

int head[];

int cnt;

int n,m;

inline void add(int u,int v,int w)

{

    cnt++;

    data[cnt].v=v;

    data[cnt].w=w;

    data[cnt].next=head[u];

    head[u]=cnt;

}

queue<int> q;

int fl[];

int value[];

signed main()

{

    cin>>n>>m;

    for(int i=;i<=m;i++)

    {

        int u,v,w;

        cin>>u>>v>>w;

        add(u,v,w);

        fl[v]++;

    }

    for(int i=;i<=n;i++)

    {

        if(fl[i]==)

        {

            q.push(i);

        }

    }

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        for(int i=head[x];i;i=data[i].next)

        {

            if(value[data[i].v]<value[x]+data[i].w)

            {

                value[data[i].v]=value[x]+data[i].w;

            }

            fl[data[i].v]--;

            if(!fl[data[i].v])

            {

                q.push(data[i].v);

            }

        }

    }

    int ans=;

    for(int i=;i<=n;i++)

    {

        ans=max(ans,value[i]);

    }

    cout<<ans<<endl;

    return ;

}

45分代码

读题，加上了-1

得到了56分的好成绩

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<cmath>

#define int long long int 

using namespace std;

struct node

{

    int u;

    int v;

    int w;

    int next;

}data[];

int head[];

int cnt;

int n,m;

inline void add(int u,int v,int w)

{

    cnt++;

    data[cnt].v=v;

    data[cnt].w=w;

    data[cnt].next=head[u];

    head[u]=cnt;

}

queue<int> q;

int fl[];

int value[];

signed main()

{

    cin>>n>>m;

    for(int i=;i<=m;i++)

    {

        int u,v,w;

        cin>>u>>v>>w;

        add(u,v,w);

        fl[v]++;

    }

    for(int i=;i<=n;i++)

    {

        if(fl[i]==)

        {

            q.push(i);

        }

    }

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        for(int i=head[x];i;i=data[i].next)

        {

            if(value[data[i].v]<value[x]+data[i].w)

            {

                value[data[i].v]=value[x]+data[i].w;

            }

            fl[data[i].v]--;

            if(!fl[data[i].v])

            {

                q.push(data[i].v);

            }

        }

    }

    int ans=;

    for(int i=;i<=n;i++)

    {

        ans=max(ans,value[i]);

    }

    if(ans==)

    {

        cout<<-<<endl;

    }

    else cout<<ans<<endl;

    return ;

}

56分代码

问了问lzt大佬

他说什么求的是1到n的最长路，而不是整张图中的最长路。。

修改，期望得分100

实际得分：67

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<cmath>

#define int long long int 

using namespace std;

struct node

{

    int u;

    int v;

    int w;

    int next;

}data[];

int head[];

int cnt;

int n,m;

inline void add(int u,int v,int w)

{

    cnt++;

    data[cnt].v=v;

    data[cnt].w=w;

    data[cnt].next=head[u];

    head[u]=cnt;

}

queue<int> q;

int fl[];

int value[];

signed main()

{

    cin>>n>>m;

    for(int i=;i<=m;i++)

    {

        int u,v,w;

        cin>>u>>v>>w;

        add(u,v,w);

        fl[v]++;

    }

    for(int i=;i<=n;i++)

    {

        if(fl[i]==)

        {

            q.push(i);

        }

    }

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        for(int i=head[x];i;i=data[i].next)

        {

            if(value[data[i].v]<value[x]+data[i].w)

            {

                value[data[i].v]=value[x]+data[i].w;

            }

            fl[data[i].v]--;

            if(fl[data[i].v]==)

            {

                q.push(data[i].v);

            }

        }

    }

    int ans=;

    for(int i=;i<=n;i++)

    {

        ans=max(ans,value[i]);

    }

    if(ans==)

    {

        cout<<-<<endl;

    }

    else cout<<value[n]<<endl;

    return ;

}

67分代码

继续问lzt大佬，

说什么要先删边再求

也就是说，在整张图中，可能存在很多入度为零的点

此时我们就需要删边（因为求1到n的最长路，和那些不是一的点有什么关系呢？？）

打个比方：如果你不删边，也不处理那些入度为零的点

就好比你想知道你谈的恋爱中哪场谈的最久，如果不处理，就成了你和你的所有前女友中，你们谈的所有恋爱中时间最久的那个。

也就是你求你谈的最长的一场恋爱，和你前女友们谈的最长的恋爱不是一个东西

好，那么我们先把除了1之外入度为零的点都放进去

跑一边拓扑排序，就达到了删边的目的

然后再把一放入队列中，进行第二遍拓扑排序

这时，到达n的最长路就是1到n的最长路

期望得分100

实际得分89..

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<cmath>

#define int long long int 

using namespace std;

struct node

{

    int u;

    int v;

    int w;

    int next;

}data[];

int head[];

int cnt;

int n,m;

inline void add(int u,int v,int w)

{

    cnt++;

    data[cnt].v=v;

    data[cnt].w=w;

    data[cnt].next=head[u];

    head[u]=cnt;

}

queue<int> q;

int fl[];

int value[];

signed main()

{

    cin>>n>>m;

    for(int i=;i<=m;i++)

    {

        int u,v,w;

        cin>>u>>v>>w;

        add(u,v,w);

        fl[v]++;

    }

    for(int i=;i<=n;i++)

    {

        if(fl[i]==)

        {

            q.push(i);

        }

    }

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        for(int i=head[x];i;i=data[i].next)

        {

            fl[data[i].v]--;

            if(fl[data[i].v]==)

            {

                q.push(data[i].v);

            }

        }

    }

    q.push();

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        for(int i=head[x];i;i=data[i].next)

        {

            if(value[data[i].v]<value[x]+data[i].w)

            {

                value[data[i].v]=value[x]+data[i].w;

            }

            fl[data[i].v]--;

            if(fl[data[i].v]==)

            {

                q.push(data[i].v);

            }

        }

    }

    int ans=;

    for(int i=;i<=n;i++)

    {

        ans=max(ans,value[i]);

    }

    if(ans==)

    {

        cout<<-<<endl;

    }

    else cout<<value[n]<<endl;

    return ;

}

89分代码

错在哪里了呢？？

再仔细读一遍代码

发现特判-1的地方写错了

ans==0是指整张图中的最长路是零

但是并不是说明了1到n之间有路

然后我们就特判一下，如果value[n]==0

那么我们就输出-1

这是因为，当ans>0时，只是说明了图中有点相连，并没有说明1到n之间有路可走

这时我们特判一下，当其是零的时候，就说明了没有路可走，那么我们就输出-1

期望得分100

实际得分100

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<cmath>

#define int long long int 

using namespace std;

struct node

{

    int u;

    int v;

    int w;

    int next;

}data[];

int head[];

int cnt;

int n,m;

inline void add(int u,int v,int w)

{

    cnt++;

    data[cnt].v=v;

    data[cnt].w=w;

    data[cnt].next=head[u];

    head[u]=cnt;

}

queue<int> q;

int fl[];

int value[];

signed main()

{

    cin>>n>>m;

    for(int i=;i<=m;i++)

    {

        int u,v,w;

        cin>>u>>v>>w;

        add(u,v,w);

        fl[v]++;

    }

    for(int i=;i<=n;i++)

    {

        if(fl[i]==)

        {

            q.push(i);

        }

    }

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        for(int i=head[x];i;i=data[i].next)

        {

            fl[data[i].v]--;

            if(fl[data[i].v]==)

            {

                q.push(data[i].v);

            }

        }

    }

    q.push();

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        for(int i=head[x];i;i=data[i].next)

        {

            if(value[data[i].v]<value[x]+data[i].w)

            {

                value[data[i].v]=value[x]+data[i].w;

            }

            fl[data[i].v]--;

            if(fl[data[i].v]==)

            {

                q.push(data[i].v);

            }

        }

    }

    int ans=;

    for(int i=;i<=n;i++)

    {

        ans=max(ans,value[i]);

    }

    if(ans==||value[n]==)

    {

        cout<<-<<endl;

    }

    else cout<<value[n]<<endl;

    return ;

}

100分代码

巴特西

洛谷 P1807 最长路_NOI导刊2010提高（07）题解

最新文章

热门文章