关于最长路——SPFA和拓扑

· · 题解

来总结下坑点

这道题我有两种做法：SPFA和拓扑

SPFA代码：

#include<queue>
#include<cstdio>
#include<cstring>
#define N 1551
#define M 50005
using namespace std;
struct edge{
    int to,val,next;
} e[M];
int h,i,m,n,t,u,v,w,hd[N],dis[N];
bool vis[N];
queue <int> q;
int cnt=0;
 void build(int u,int v,int w)
 {
    cnt++;
    e[cnt].to=v;
    e[cnt].val=w;
    e[cnt].next=hd[u];
    hd[u]=cnt;
 }
int main()
{
    memset(dis,-1,sizeof(dis));
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        build(u,v,w);
    }
    q.push(1);
    dis[1]=0;
    vis[1]=true;
    while(!q.empty())
    {
        h=q.front();q.pop();
        vis[h]=false;
        for(i=hd[h];i;i=e[i].next)
        {
            t=e[i].to;
            if(dis[t]<dis[h]+e[i].val)
            {
                dis[t]=dis[h]+e[i].val;
                if(!vis[t])
                {
                    vis[t]=true;
                    q.push(t);
                }
            }
        }
    }
    printf("%d",dis[n]);
    return 0;
}

如果你明白spfa的原理（而不是代码纯靠背），那么过这道题是特别轻松的——

直接把if(dis[t]>dis[h]+e[i].val)的大于号改成小于号，dis数组初始化为0（记得改下数组大小）

你就AC了

原理很简单，和最短路一模一样，只不过改变了大小比较的方式而已

在这里也整理一下其他大佬的各种做法——

取负边权跑最短路，输出时再取反即可。

开特殊队列

队列中存结构体，重载运算符……

后头两种我也不懂……只是听别人说的……

总之取负边那个还是比较实用的

但是，能改一个符号过的事，何必那么麻烦对吧。

spfa部分总结完毕

拓扑代码：

#include<queue>
#include<cstdio>
#include<cstring>
#define N 1551
#define M 50005
using namespace std;
struct edge{
    int to,val,next;
} e[M];
int h,i,m,n,t,u,v,w,hd[N],dis[N],ind[N];
bool vis[N];
queue <int> q;
int cnt=0;
 void build(int u,int v,int w)
 {
    cnt++;
    e[cnt].to=v;
    e[cnt].val=w;
    e[cnt].next=hd[u];
    hd[u]=cnt;
 }
int main()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        build(u,v,w);
        ind[v]++;
    }
    for(i=1;i<=n;i++)
     if(!ind[i]) q.push(i);//一开始在push的同时把vis也设成true了，不对，我们一开始只默认从1出发去处理其它边
    vis[1]=true;dis[n]=-1;
    while(!q.empty())
    {
        h=q.front();q.pop();
        for(i=hd[h];i;i=e[i].next)
        {
            t=e[i].to;
            ind[t]--;
            if(vis[h])//受SPFA影响，这里一开始写的if(!vis[t])，但事实上这是不对的，每个点可被重复计算。
            //只要这个点的前一个点访问过就可以用这个点去松弛，故为if(vis[h])
            {
                dis[t]=max(dis[t],dis[h]+e[i].val);
                vis[t]=true;
            }
            if(!ind[t]) q.push(t);
        }
    }
    printf("%d",dis[n]);
    return 0;
}

坑点在代码里都总结了

SPFA:61ms,1.07MB Topsort:34ms,1.14MB

毕竟一个是O(Ke),一个是O(n+m)，速度还是差不少的，稠密图更能体现出来 大部分情况下使用SPFA，DAG上一定要用拓扑的。

好啦总结完毕